PAT甲級1013題解——并查集+路徑壓縮-有解無憂

題目分析：

本題初步瀏覽題目就知道是并查集的模板題，資料輸入范圍N為1~1000，則M的范圍為0~1000^2，通過結構體記錄每一對連線的關系，p[]陣列記錄每個節點的跟，對于k次查詢，每次都要重新維護p[]陣列，而每次的區別在于都要排除被占領的節點重新維護p[]陣列的節點的鏈接關系，而最終的答案就是集合數-2（占領點一定是單獨的集合，n個集合需要n-1條邊就能相連）

 1 #include<iostream>
 2 using namespace std;
 3 
 4 struct Node{
 5     int from;
 6     int to;
 7 }a[1000005];
 8 int p[1005];
 9 int n, m, k;
10 
11 int find(int x){
12     int y = x;
13     while(p[x] != x){
14         x = p[x];
15     }
16     //路徑壓縮 此時x是根 
17     while(p[y] != x){
18         int t = y;            //對于路徑上的每個y節點都要保留一下 
19         y = p[y];            //此時我們還是按照上述的順序去查詢根 
20         p[t] = x;            //y已經變的p[y]的值，而t則記錄了之前y的值 而p[之前的y]已經用不到了，我們將其路徑壓縮，把它的跟直接變為x 
21     }
22     return x;
23 }
24 
25 void Union(int x, int y){
26     int fx = find(x);
27     int fy = find(y);
28     if(fx != fy){
29         p[fx] = fy;
30     }    
31 }
32 
33 void init(int occupy){
34     for(int i = 1; i <= n; i++) p[i] = i;
35     for(int i = 1; i <= m; i++){
36         //根據a中的一對一對的關系維護并查集 同時注意被占領的城市不參與其中
37         if(a[i].from != occupy && a[i].to != occupy){
38             Union(a[i].from, a[i].to);
39         }
40     }
41 }
42 
43 void run(){
44     int ans = 0;
45     for(int i = 1; i <= n; i++){
46         if(p[i] == i){
47             ans++;
48         }
49     }    
50     printf("%d\n", ans - 2);
51 } 
52 
53 int main(){
54     while(scanf("%d%d%d", &n, &m, &k) != EOF){
55         for(int i = 1; i <= m; i++){
56             scanf("%d%d", &a[i].from, &a[i].to);            
57         }
58         int occupy; 
59         for(int i = 1; i <= k; i++){
60             scanf("%d", &occupy);
61             //每次都要初始化并查集 
62             init(occupy);
63             //獲取每次至少要添加的線條數 
64             run();
65         }
66     }
67     return 0;
68 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139973.html

標籤：其他

上一篇：PAT甲級1012題解——選擇一種合適資料存盤方式能使題目變得更簡單

下一篇：2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)-E. Explosion Exploit-概率+狀壓dp