題目連結
題目大意：
第一行輸入表示這個網路有n點，後最多n行表達網路的連接方式，這個網路已是competely connected。求這個網路的critical point。
（註：critical point表示這個點拿掉之後，這個網路就不會完全連接）
解題思路：
這題我覺得最麻煩的是讀取輸入= =
讀取進來後連接方式已adjacency matrix表示
後一個一個點拿拿看，用DFS跑，會出現2個tree以上的就是critical point。
參考：
【C++】讀取整行輸入並依空白分割
http://celinechiu0809.blogspot.tw/2015/05/c.html
【C++】DFS簡單範例
http://celinechiu0809.blogspot.tw/2015/05/cdfs.html
Code
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 <cstdio>#include <cstdlib>#include <sstream>#include <iostream>using namespace std;int adj_matrix[100][100], n, color[100];void initiate(){ for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) adj_matrix[i][j] = 0; }}void dfs_visit(int v){ color[v] = 1; for (int u=1; u<=n; u++) { if (color[u]==0 && adj_matrix[v][u]==1) dfs_visit(u); } color[v] = 2;}int main(){ string line; int tmp; while (getline(cin, line)) { istringstream in(line); in>>n; if (n==0) break; tmp = n+1; initiate(); while (tmp--) { getline(cin, line); istringstream in(line); int a=0, b,flag=0; while (in >> b){ if (flag==0){ a = b; flag = 1; } else adj_matrix[a][b] = adj_matrix[b][a] = 1; } if (a==0) break; } int critical_point=0, tree_count; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) color[j]=0; color[i] = 2; tree_count = 0; for (int j=1; j<=n; j++) { if (color[j]==0){ dfs_visit(j); tree_count++; } } if (tree_count>1) critical_point++; } printf("%d\n", critical_point); } return 0;} |
