PAT A 1013. Battle Over Cities (25)【并查集】

https://www.patest.cn/contests/pat-a-practise/1013
思路：并查集合并
 1 #include<set>  
 2 #include<map>  
 3 #include<queue>  
 4 #include<algorithm>  
 5 #include<string>  
 6 #include<string.h>  
 7 using namespace std;
 8 
 9 int n;//number of city  
10 int m;//number of edge  
11 int k;//number of query  
12 
13 typedef struct  Edge
14 {
15     int v;
16     Edge(int _v) :v(_v){};
17 }Edge;
18 typedef struct Node
19 {
20     int parent;
21 }Node;
22 vector<Node> city;
23 void InitSet()
24 {
25     city.resize(n);
26     for (int i = 0; i < n; i++)
27         city[i].parent = i;//独立离散连通域
28 }
29 
30 int FindSet(int x)
31 {
32     if (city[x].parent != x)
33     {
34         int top = FindSet(city[x].parent);
35         city[x].parent = top;
36     }
37     return city[x].parent;
38 }
39 void UnionSet(int x, int y)
40 {
41     int a = FindSet(x);
42     int b = FindSet(y);
43     if (a != b)city[a].parent = b;
44 }
45 int main()
46 {
47     scanf("%d%d%d", &n, &m, &k);
48     vector<vector<Edge>> edge;
49     edge.resize(n);
50     for (int i = 0; i < m;i++)
51     {
52         int a, b;
53         scanf("%d%d", &a, &b);
54         a--, b--;
55         edge[a].push_back(Edge(b));
56         edge[b].push_back(Edge(a));
57     }
58     for (int i = 0; i < k; i++)
59     {
60         int q;
61         scanf("%d", &q);
62         q--;
63         InitSet();
64         for (int u = 0; u < n; u++)
65         {
66             for (int j = 0; j < edge[u].size(); j++)
67             {
68                 int v = edge[u][j].v;
69                 if (u != q&&v != q)UnionSet(u, v);
70             }
71         }
72         set<int> parentSet;
73         for (int j = 0; j < n; ++j)
74             //must be care for this, for consistency we must get the root via FindSet function instead of city[j].parent  
75             parentSet.insert(FindSet(j));
76         printf("%d
", parentSet.size() - 2);
77     }
78     return 0;
79 }
80 
81 
82 
83 
84