文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing

分析：并查集題目。

不清楚并查集的小伙伴，請移步并查集原理并查集板子:acwing836. 合并集合。

題意：給定一個連通圖，當刪掉任意1個點后，問剩下幾個連通塊。
解題：

用結構體存每條邊，結構體存的是兩個端點；e[i].a 和e[i].b就是第i條邊的兩個端點。

總共n個點，對于每次詢問x，就是問刪掉x這個點后，還有幾個連通塊。刪掉x后，還剩下n-1個點，先初始化為n-1個連通塊。變量cnt用來統計連通塊的數量，cnt初始化為cnt==n-1

遍歷每一條邊，找到和點x無關的邊的兩端點，將其放入一個集合中（因為一條邊的兩端點本身就是一個連通塊嘛），同時，將cnt- -。這樣，遍歷完所有的邊，也就記錄下來連通塊的數量cnt

題目所求：建邊的數量就是cnt-1

AC代碼

#include<bits/stdc++.h> using namespace std; const int N = 1e3+10,M= 500010; int n , m, k; int p[N]; struct Edge{int a,b; }e[M];//并查集模板，找根 int find(int x){if(p[x] != x) p[x] =find(p[x]);return p[x]; } int main(){scanf("%d%d%d",&n,&m,&k);//讀邊for(int i = 0; i<m ; i ++) scanf("%d%d",&e[i].a,&e[i].b);//讀詢問while(k--){int x;scanf("%d",&x);//初始化并查集，n個集合for(int i =1; i<=n; i++) p[i] = i;int cnt = n-1; //統計不同連通塊的數量//遍歷每一條邊for(int i =0 ;i<m; i++){int a = e[i].a,b =e[i].b;//如果該邊的兩個端點和刪掉的點都沒有關系if( a != x && b != x){//看是否屬于同一個集合int pa = find(a) ,pb = find(b);//不屬于的話，合并成一個集合，同時不同連通塊的數量--。if(pa != pb){p[pa] =pb; cnt --;}}}//最終的建邊數量，等于不同連通塊數量-1；printf("%d\n",cnt-1);} }

題目鏈接

PAT甲級1013 Battle Over Cities
https://www.acwing.com/problem/content/1487/

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的PAT甲级1013 Battle Over Cities：[C++题解]并查集、结构体存边的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。