題目連結
題目大意：
給人名，誰可以打給誰。後找出可以互相打電話的圈圈
題目思路：
這題就是找Strongly connected component
應該可以有三種解法
1. Floyd Warshell
2. DFS
3. Disjoint_Set
以下Code 示範第1種
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <cstdio>#include <queue>#include <string.h>#define MAX 26#define INF 10000using namespace std;char people[MAX][MAX];int adj[MAX][MAX];int print_flag[MAX];int name_count, n;void init(){ name_count = 0; for (int i=0; i< n; i++){ for (int j=0; j< n; j++) adj[i][j] = INF; adj[i][i] = 0; print_flag[i] = 0; }}int check_name_exist(char *name){ for (int i=0; i< name_count; i++) if (!strcmp(name, people[i])) return i; return -1;}void floyd_warshell(){ for (int k=0; k< n; k++) for (int i=0; i< n; i++) for (int j=0; j< n; j++) if (adj[i][j]>adj[i][k]+adj[k][j]) adj[i][j] = adj[i][k]+adj[k][j];}void print(){ for (int i=0; i< n; i++){ if (!print_flag[i]){ print_flag[i] = 1; printf("%s", people[i]); for (int j=0; j< n; j++) { if (adj[i][j]< INF && adj[j][i]< INF && !print_flag[j]){ print_flag[j] = 1; printf(", %s", people[j]); } } printf("\n"); } }}int main() { int m, id1, id2, case_count = 1; char name1[MAX], name2[MAX]; while (scanf("%d %d", &n, &m) && n) { init(); if (case_count==1) printf("Calling circles for data set %d:\n", case_count++); else printf("\nCalling circles for data set %d:\n", case_count++); while (m--) { scanf("%s %s", name1, name2); id1 = check_name_exist(name1); id2 = check_name_exist(name2); if (id1==-1){ strcpy(people[name_count], name1); id1 = name_count++; } if (id2==-1){ strcpy(people[name_count], name2); id2 = name_count++; } adj[id1][id2] = 1; } floyd_warshell(); print(); } return 0;} |
