글 읽기 - 3977번, 축구 전술 문제 33%에서 계속 틀렸습니다가 뜨네요..

rjf1138 3년 전 0

3977번, 축구 전술 문제 33%에서 계속 틀렸습니다가 뜨네요..

타잔 알고리즘 사용하였는데, 정점 번호가 1부터 N까지가 아닌 0부터 N-1에서 오류가 나는 것 같애서 그 부분에 유의하면서

코딩을 하였는데도 33%에서 틀렸습니다가 뜨네요.

혹시 반례나 오류 있다면 지적 부탁드립니다ㅠㅠㅠ

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring> //memset
using namespace std;
#define MAX 100001

int T, N, M;
int id, pa[MAX];
bool finished[MAX];
int inDegree[MAX];
int group[MAX];
vector<int> graph[MAX];
vector<vector<int>> SCC;
stack<int> s;

int dfs(int cur) {
	pa[cur] = ++id;
	s.push(cur);
	int parent = pa[cur];
	
	for (int i = 0; i < graph[cur].size(); ++i) {
		int next = graph[cur][i];
		if (pa[next] == 0) parent = min(parent, dfs(next));
		else if (!finished[next]) parent = min(parent, pa[next]);
	}

	if (parent == pa[cur]) {
		vector<int> scc;
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			group[t] = SCC.size();
			if (t == cur) break;
		}
		SCC.push_back(scc);
	}
	return parent;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	for (int t = 0; t < T; ++t) {
		memset(pa, 0, sizeof(pa));
		memset(finished, false, sizeof(finished));
		memset(inDegree, 0, sizeof(inDegree));
		memset(group, -1, sizeof(group));
		SCC.clear();
		cin >> N >> M;

		for (int i = 0; i < N; ++i)
			graph[i].clear();
		
		int from, to;
		for (int i = 0; i < M; ++i) {
			cin >> from >> to;
			graph[from].push_back(to);
		}

		for (int i = 0; i < N; ++i) 
			if (pa[i] == 0) dfs(i);
		

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < graph[i].size(); ++j) {
				int next = graph[i][j];
				if (group[j] != group[next]) inDegree[group[next]]++;
			}
		}

		int cnt = 0;
		vector<int> answer;
		for (int i = 0; i < SCC.size(); ++i) {
			if (inDegree[i] == 0) {
				cnt++;
				for (int j = 0; j < SCC[i].size(); ++j)
					answer.push_back(SCC[i][j]);
			}
		}
	
		if (cnt != 1) {
			cout << "Confused"<<'\n';
		}
		else {
			sort(answer.begin(), answer.end());
			for (int i = 0; i < answer.size(); ++i)
				cout << answer[i] << '\n';
		}
		cout << '\n';
	}
	return 0;
}

kth990303 2년 전 0

늦었지만 조금이나마 도움되시라고 반례 드립니다.

1
2 1
1 0
ans: 1
wrong: Confused

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3977번, 축구 전술 문제 33%에서 계속 틀렸습니다가 뜨네요..

rjf1138 3년 전 0

kth990303 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말