1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
int v, e, a, b;
// 그래프의 인접 리스트 표현
vector<vector<int>> adj(10004);
// 각 정점의 컴포넌트 번호. 컴포넌트 번호는 0부터 시작하며
// 같은 강결합 컴포넌트에 속한 정점들의 컴포넌트 번호가 같다.
vector<int> sccID;
// 각 정점의 발견 순서
vector<int> discovered;
// 정점의 번호를 담는 스택
stack<int> st;
int sccCounter, vertexCounter;
// here를 루트로 하는 서브트리에서 역방향 간선이나 교차 간선을
// 통해 갈 수 있는 정점 중 최소 발견 순서를 반환한다.
// (이미 SCC로 묶인 정점으로 연결된 교차 간선은 무시한다.)
int scc(int here) {
// 이 코드에서 here과 there은 u,v 즉 연결된 정점이라고 생각하면 편하다
int ret = discovered[here] = vertexCounter++;
// 스택에서 here를 넣는다. here의 후손들은 모두 스택에서 here 후에 들어간다.
st.push(here);
for (int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i];
// (here, there)가 트리 간선
if (discovered[there] == -1) ret = min(ret, scc(there)); // 아직 방문하지 않았다면
// there가 무시해야 하는 교차 간선이 아니라면
else if (sccID[there] == -1) {
ret = min(ret, discovered[there]);
}
}
// here에서 부모로 올라가는 간선을 끊어야 할지 확인한다.
if (ret == discovered[here]) {
//here를 루트로 하는 서브트리에 남아 있는 정점들을 전부 하나의 컴포넌트로 묶는다.
while (true) {
int t = st.top();
st.pop();
sccID[t] = sccCounter; // sccID의 각 index에는 각 정점이 몇 번째 컴포넌트인지 들어있다.
if (t == here) break;
}
++sccCounter;
}
return ret;
}
// tarjan의 SCC알고리즘
vector<int> tarjanSCC() {
// 배열들을 전부 초기화
sccID = discovered = vector<int>(adj.size(), -1);
// 카운터 초기화
sccCounter = vertexCounter = 0;
// 모든 정점에 대해 scc() 호출
for (int i = 0; i <= v; i++)if (discovered[i] == -1) scc(i);
return sccID;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> v >> e;
for (int i = 0; i < e; i++) {
cin >> a >> b;
adj[a].push_back(b);
}
vector<int> temp = tarjanSCC();
cout << sccCounter - 1 << "\n";
bool check[10004];
memset(check, false, sizeof(check));
for (int i = 1; i <= v; i++) {
if (check[i] == false) {
check[i] = true;
vector<int>ans;
ans.push_back(i);
for (int k = i; k <= v; k++) {
if (check[k] == false && temp[i]==temp[k]) {
ans.push_back(k);
check[k] = true;
}
}
sort(ans.begin(), ans.end());
for (int j = 0; j < ans.size(); j++) {
cout << ans[j] << " ";
}
cout << "-1" << "\n";
}
}
}
|
cs |
'Koala - 1기' 카테고리의 다른 글
휴리스틱 알고리즘(Heuristic Algorithm) (1) | 2020.12.27 |
---|---|
백준 17134번 - 르모앙의 추측 (0) | 2020.12.27 |
백준 1197번 - 최소 스패닝 트리 (0) | 2020.12.27 |
백준 2621번 - 카드게임 (0) | 2020.12.27 |
스터디 세부 계획 (0) | 2020.08.16 |