백준 3977번 축구 전술

사용한 알고리즘 : SCC

​

문제는 각 점들을 SCC로 묶었을 때, indegree가 0인 (들어오는 edge가 없는) SCC가 딱 1개 있는지 여부였습니다. (2개 있다면 서로는 서로에게 못가니, 한 지점에서 다른 모든 지점으로 갈 수 있는지 묻는 물음에 부합하지 못합니다.)

​

우선 각 점들을 SCC로 묶었습니다.

이후 모든 점들을 돌면서, 그 점의 자식이 자신과 다른 SCC 에 있는지 확인하고,

만약 다른 SCC에 있는 경우, 자식이 속한 SCC의 indegree++ 해주었습니다.

이후 SCC를 모아놓은 벡터를 돌며 indegree가 0 인 SCC가 1개인지 확인 후,

1개인 경우 답을 말하고,

아닌 경우 "Confused"를 외쳐주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 100001;
	int T, N, M, cnt, SN, check, sn[MAX], dfsn[MAX], indegree[MAX];
	vector<int> adj[MAX];
	bool finished[MAX];
	bool visited[MAX];
	stack<int> S;
	vector<vector<int>> SCC;
	int DFS(int curr){
	dfsn[curr] = ++cnt;
	S.push(curr);
	int result = dfsn[curr];
	for (int next: adj[curr]){
	if(dfsn[next] == 0) result = min(result, DFS(next));
	else if(!finished[next]) result = min(result, dfsn[next]);
	}
	if(result == dfsn[curr]){
	vector<int> currSCC;
	while(1){
	int t = S.top();
	S.pop();
	currSCC.push_back(t);
	finished[t] = true;
	sn[t] = SN;
	if(t==curr) break;
	}
	SCC.push_back(currSCC);
	SN++;
	}
	return result;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	cin >> N >> M;
	bool flag = false;
	check = -1;
	cnt = 0;
	SCC.clear();
	SN = 0;
	while(!S.empty()) S.pop();
	for (int i = 0; i < N; ++i) adj[i].clear();
	memset(finished,false,sizeof(finished));
	memset(indegree,0,sizeof(indegree));
	memset(dfsn,0,sizeof(dfsn));
	memset(sn,-1,sizeof(sn));
	for (int i = 0; i < M; ++i){
	int a, b;
	cin >> a >> b;
	adj[a].push_back(b);
	}
	for (int i = 0; i < N; ++i)
	if(dfsn[i]==0) DFS(i);
	for (int i = 0; i < N; ++i)
	for (int next: adj[i])
	if(sn[i]!=sn[next]) indegree[sn[next]]++;
	for (int i = 0; i < SCC.size(); ++i){
	if(indegree[i]==0){
	if(check==-1) check = i;
	else flag = true;
	}
	}
	if(flag){
	cout << "Confused" << '\n';
	}
	else{
	sort(SCC[check].begin(),SCC[check].end());
	for (int i = 0; i < SCC[check].size(); ++i)
	cout << SCC[check][i] << '\n';
	}
	cout << '\n';
	}
	return 0;
	}

view raw BOJ 3977.cpp hosted with ❤ by GitHub

​