(BOJ) 3799 축구 전술

문제: https://www.acmicpc.net/problem/3977

 

문제 풀이:

scc를 구하는데 각 점들의 scc번호를 p배열에 저장함

scc를 구하는 dfs 중 a->b를 가리켰는데 b가 이미 visit이라면 

  case1: b가 다른 scc인 경우 (p[a]!=p[b]) degree[a]++ 

  case2: b가 같은 scc인 경우는 그냥 패스

 

이렇게 했을 때 degree가 0인 scc가 한 개이면 그 scc를 정렬해서 출력하면 되고

두 개 이상이면 "Confused" 출력

 

소스 코드:

int tc, n, m,p[100001],degree[100001];
bool visit[100001];
vector<vector<int>> adj,adj2;
stack<int> st;
vector<vector<int>> scc;
void dfs(int v,bool t) {
	if (visit[v]) return;
	visit[v] = true;
	for (int i : adj[v]) {
		dfs(i,t);
	}
	if(t) st.push(v);
}
void rdfs(int v,int t) {
	if (visit[v]) return;
	visit[v] = true;
	scc[t].push_back(v);
	p[v] = t;
	for (int i : adj2[v]) {
		if (visit[i]) {
			if (p[v] != p[i]) degree[t]++;
			continue;
		}
		rdfs(i,t);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		memset(degree, 0, sizeof(degree));
		memset(visit, false, sizeof(visit));
		adj.clear();
		adj2.clear();
		adj.resize(n + 1);
		adj2.resize(n + 1);
		scc.clear();
		for (int i = 0; i < m; i++) {
			int q, w;
			cin >> q >> w;
			adj[q].push_back(w);
			adj2[w].push_back(q);
		}
		while (!st.empty()) st.pop();
		for (int i = 0; i < n; i++) {
			if (visit[i])continue;
			dfs(i, true);
		}
		memset(visit, false, sizeof(visit));

		int tmp = 0;
		int res = -1;
		bool chk = true;
		while (!st.empty()) {
			int cur = st.top();
			st.pop();
			if (visit[cur]) continue;
			scc.resize(++tmp);
			rdfs(cur,tmp-1);
			if (degree[tmp - 1] == 0) {
				if (res != -1) {
					cout << "Confused\n";
					chk=false;
					break;
				}
				res = tmp - 1;
			}
		}
		if (chk) {
			sort(scc[res].begin(), scc[res].end());
			int len = scc[res].size();
			for (int j = 0; j < len; j++) {
				cout << scc[res][j] << '\n';
			}
		}
		cout << '\n';
	}

	return 0;
}