[BOJ 3977]
문제 바로가기 : https://www.acmicpc.net/problem/3977
비슷한 유형 문제, BOJ 4196 : https://www.acmicpc.net/problem/4196
문제 설명은 위 링크에서 확인해주시길 바랍니다.
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //3977 | |
| #include <iostream> | |
| #include <string> | |
| #include <cstring> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <deque> | |
| #include <queue> | |
| #include <stack> | |
| #include <cmath> | |
| #include <algorithm> | |
| #include <map> | |
| using namespace std; | |
| #define INF 987654321 | |
| #define MAXSIZE 100001 | |
| typedef long long ll; | |
| vector<int> node[MAXSIZE]; | |
| vector<vector<int>> SCC; | |
| int chk[MAXSIZE], degree[MAXSIZE], uni[MAXSIZE]; | |
| bool fin[MAXSIZE]; | |
| stack<int> s; | |
| int id, sccnum; | |
| void init() { | |
| memset(chk, 0, sizeof(chk)); | |
| memset(degree, 0, sizeof(degree)); | |
| memset(fin, false, sizeof(fin)); | |
| memset(uni, 0, sizeof(uni)); | |
| SCC.clear(); | |
| while (!s.empty()) s.pop(); | |
| id = 0; sccnum = 0; | |
| } | |
| int dfs(int cur) { | |
| chk[cur] = ++id; | |
| s.push(cur); | |
| int parent = chk[cur]; | |
| for (auto& next : node[cur]) { | |
| if (chk[next] == 0) parent = min(parent, dfs(next)); | |
| else if (!fin[next]) parent = min(parent, chk[next]); | |
| } | |
| //부모일 때 하나의 SCC 생성 | |
| if (chk[cur] == parent) { | |
| vector<int> subSCC; | |
| sccnum++; | |
| while (1) { | |
| int node = s.top(); s.pop(); | |
| subSCC.push_back(node); | |
| fin[node] = true; | |
| uni[node] = sccnum; //어느 집합에 있는지 체크 | |
| if (chk[node] == parent) break; | |
| } | |
| sort(subSCC.begin(), subSCC.end()); | |
| SCC.push_back(subSCC); | |
| } | |
| return parent; | |
| } | |
| int main() { | |
| cin.tie(nullptr); | |
| cout.tie(NULL); | |
| ios_base::sync_with_stdio(false); | |
| int t; cin >> t; | |
| while (t--) { | |
| init(); | |
| int V, E; cin >> V >> E; | |
| while (E--) { | |
| int a, b; cin >> a >> b; | |
| node[a].push_back(b); //a->b | |
| } | |
| for (int i = 0; i < V; i++) { | |
| if (chk[i] == 0) dfs(i); | |
| } | |
| //answer | |
| for (int i = 0; i < V; i++) { | |
| for (auto& next : node[i]) { | |
| //same union | |
| if (uni[i] == uni[next]) continue; | |
| degree[uni[next]]++; | |
| } | |
| } | |
| int zerodegree = 0; //1개가 아니면 confused | |
| int wherescc = -1; | |
| for (int i = 1; i <= sccnum; i++) | |
| if (degree[i] == 0) { | |
| zerodegree++; | |
| wherescc = i; | |
| } | |
| if (zerodegree > 1 || wherescc == -1) { | |
| cout << "Confused" << '\n'; | |
| } | |
| else { | |
| /* | |
| for (int i = 0; i < V; i++) { | |
| if (uni[i] == wherescc) | |
| cout << i << '\n'; | |
| } | |
| */ | |
| for (auto& a : SCC[wherescc - 1]) cout << a << '\n'; | |
| } | |
| cout << '\n'; | |
| for (int i = 0; i < V; i++) node[i].clear(); | |
| } | |
| return 0; | |
| } |
reviewPermalink
BOJ 4196에서 SCC와 위상 정렬을 함께 사용했었다. 이 문제도 비슷하다.
문제에서 다른 모든 구역에 도달할 수 있는 시작 구역이라는 표현을 썼다. SCC 개념이 이용됐다는걸 알 수 있다.
그럼 모두 1개의 SCC에 있어야 한다는 말인가? 싶지만 그렇지 않다. 다른 SCC여도 도달할 수 있다!
SCC들의 묶음으로 모아놓았을 때 SCC간의 간선이 있어야 한다. 그렇다면 무조건 degree가 0인 SCC가 발생한다.
여기서는 degree가 0인 SCC가 여러개가 되면 모든 구역에 도달할 수 없다.
따라서 degree가 0이 되는 SCC가 1개일 때 그 SCC의 속한 노드들을 출력하면 되고, 그렇지 않으면 Confused를 출력한다.
int zerodegree = 0; //1개가 아니면 confused
int wherescc = -1;
for (int i = 1; i <= sccnum; i++)
if (degree[i] == 0) {
zerodegree++;
wherescc = i;
}
if (zerodegree > 1 || wherescc == -1) {
cout << "Confused" << '\n';
}
else {
/*
for (int i = 0; i < V; i++) {
if (uni[i] == wherescc)
cout << i << '\n';
}
*/
for (auto& a : SCC[wherescc - 1]) cout << a << '\n';
}
cout << '\n';
주석으로 처리한 부분은 어느 집합에 담겼는지 알려주는 배열(uni[])에서 가져와 출력하는 방식이고
그 아랫줄은 SCC를 가져와서 속한 노드를 출력하는 방식이다. 어느 방법으로 해도 답은 똑같다.
댓글남기기