PTA A_1013 Battle Over Cities

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805500414115840

解：
DFS+邻接表

1. #include<cstdio>
   
2. #include<vector>
   
3. #include<algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int n, m, k;
   
8. vector<int> adj[1010];
   
9. bool vis[1010];
   
10. 
    
11. void DFS(int x)
    
12. {
    
13.     vis[x] = true;
    
14. 
    
15.     for (int i = 0; i < adj[x].size(); i++)
    
16.         if (!vis[adj[x][i]]) DFS(adj[x][i]);
    
17. }
    
18. 
    
19. int DFS_Traverse(void)
    
20. {
    
21.     int num = 0;
    
22. 
    
23.     for (int i = 1; i <= n; i++)
    
24.         if (!vis[i] && ++num) DFS(i);
    
25. 
    
26.     return num;
    
27. }
    
28. 
    
29. int main(void)
    
30. {
    
31.     scanf("%d %d %d", &n, &m, &k);
    
32. 
    
33.     while (m--)
    
34.     {
    
35.         int v1, v2;
    
36. 
    
37.         scanf("%d %d", &v1, &v2);
    
38. 
    
39.         adj[v1].push_back(v2);
    
40.         adj[v2].push_back(v1);
    
41.     }
    
42. 
    
43.     while (k--)
    
44.     {
    
45.         int check;
    
46. 
    
47.         scanf("%d", &check);
    
48. 
    
49.         fill(vis, vis + n + 1, false);
    
50.         vis[check] = true;
    
51. 
    
52.        printf("%d\n", DFS_Traverse() - 1);
    
53.     }
    
54. 
    
55.     return 0;
    
56. }

复制代码