트리
문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다.
연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다.
그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다.
예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.
그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다.
다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다.
정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.
출력
입력으로 주어진 그래프에 트리가 없다면 “No trees.”를, 한 개라면 “There is one tree.”를,
T개(T > 1)라면 “A forest of T trees.”를 테스트 케이스 번호와 함께 출력한다.
풀이
풀이 방법으로 유니온 파인드와 DFS가 둘 다 떠올라서 각각 해봤다.
DFS로 할 때는 이미 지난 정점을 또 지나면 그 그래프틑 사이클이 있는 그래프가 된다.
유니온 파인드로 할 때는 주어진 간선들로 유니온 한 다음, 부모 배열 값의 종류를 확인하면 된다.
이 때 유니온 과정에서 주어진 두 점이 이미 부모가 같다면 사이클이 생기는 것이다.
우선 DFS를 이용한 트리 판별이다.
처음 인접 리스트를 이용한 방법이 생각이 안나서 인접 배열을 사용했다.
무방향 그래프라 간선 연결이 양쪽으로 되는데, DFS 함수가 실행될 때 이 부분을 생각해야 한다.
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
t=0;
while(1){
t++;
cin >> n >> m;
if(n==0 && m==0)break;
vector<vector<int>> graph(n+1, vector<int>(n+1, 0));
vector<bool> check(n+1, 0);
for(int i=0;i<m;i++){
cin >> a >> b;
graph[a][b]=1;
graph[b][a]=1;
}
bool flag = 1;
function <void(int)> dfs=[&](int k){
check[k]=1;
for(int i=1;i<n+1;i++){
if(graph[k][i]==1 && !check[i]){
graph[i][k]=0;
dfs(i);
}
else if(graph[k][i]==1)flag=0;
}
};
int cnt=0;
for(int i=1;i<=n;i++){
flag = 1;
if(!check[i]){
dfs(i);
if(flag)cnt++;
}
}
cout << "Case " << t << ": ";
if(cnt==0){
cout << "No trees.\n";
}
else if(cnt==1){
cout << "There is one tree.\n";
}
else{
cout << "A forest of " << cnt << " trees.\n";
}
}
return 0;
}
밑에가 인접 리스트를 사용한 방법이다.
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
t=0;
while(1){
t++;
cin >> n >> m;
if(n==0 && m==0)break;
vector<vector<int>> graph(n+1);
vector<bool> check(n+1, 0);
for(int i=0;i<m;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bool flag = 1;
function <void(int, int)> dfs=[&](int k, int pre){
check[k]=1;
for(int i=0;i<graph[k].size();i++){
if(!check[graph[k][i]]){
dfs(graph[k][i], k);
}
else if(pre!=graph[k][i])flag=0;
}
};
int cnt=0;
for(int i=1;i<=n;i++){
flag = 1;
if(!check[i]){
dfs(i, 0);
if(flag)cnt++;
}
}
cout << "Case " << t << ": ";
if(cnt==0){
cout << "No trees.\n";
}
else if(cnt==1){
cout << "There is one tree.\n";
}
else{
cout << "A forest of " << cnt << " trees.\n";
}
}
return 0;
}
인접 배열은 DFS가 (k,i)에 실행된다면 (i,k)방향 연결은 지워줬다.
인접 리스트는 DFS 인자로 이전 값을 받아, 바로 전 정점을 확인하는 과정을 없앴다.
마지막으로 유니온 파인드를 이용한 방법이다.
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
char ch;
t=0;
while(1){
t++;
cin >> n >> m;
if(n==0 && m==0)break;
vector<vector<int>> parent(n+1, vector<int>(2, 0));
vector<int> high(n+1, 1);
for(int i=1;i<=n;i++){
parent[i][0]=i;
}
function <int(int)> find = [&](int v){
if(v==parent[v][0]) return v;
return parent[v][0] = find(parent[v][0]);
};
function <void(int, int)> uni = [&](int a, int b){
int u = find(a);
int v = find(b);
if(u==v){
parent[u][1]=1;
return; // 트리가 아니라는 거~
}
if(high[u]<high[v]) swap(u,v);
parent[v][0]=u;
if(high[u]==high[v])high[u]++;
};
for(int i=0;i<m;i++){
cin >> a >> b;
uni(a,b);
}
vector<int> check(n+1, 0);
for(int i=1;i<=n;i++){
if(find(i)!=parent[i][0]){
parent[i][0]=find(i);
}
if(!parent[parent[i][0]][1]){
check[parent[i][0]]++;
}
}
int cnt=0;
for(int i=1;i<=n;i++){
if(check[i]>0)cnt++;
}
cout << "Case " << t << ": ";
if(cnt==0){
cout << "No trees.\n";
}
else if(cnt==1){
cout << "There is one tree.\n";
}
else{
cout << "A forest of " << cnt << " trees.\n";
}
}
return 0;
}
parent배열을 2차원 배열로 만들어서 사이클이 만들어진다면 체크를 해줬다.
parent 배열의 값을 모두 root 값으로 만든 다음, root의 개수를 세면 된다.