题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805063963230208
题意:给n个顶点,m条边,问每次删除一个点会不会破坏图的连通性。
思路:用dfs/bfs求图的连通分量个数,每次求出删除点之前和之后的连通分量数cnt、cnt1,若cnt1>cnt+1,则破坏了连通性;否则就没有破坏连通性。
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,k,t1,t2,cnt,cnt1; 5 int a[505][505],vis[505]; 6 queue<int> q; 7 8 void bfs(int p){ 9 q.push(p); 10 while(!q.empty()){ 11 int nw=q.front(); 12 q.pop(); 13 for(int i=0;i<n;++i) 14 if(!vis[i]&&a[nw][i]){ 15 vis[i]=1; 16 q.push(i); 17 } 18 } 19 } 20 21 int getc(){ 22 int res=0; 23 memset(vis,0,sizeof(vis)); 24 for(int i=0;i<n;++i) 25 if(!vis[i]){ 26 vis[i]=1; 27 ++res; 28 bfs(i); 29 } 30 return res; 31 } 32 33 int main(){ 34 scanf("%d%d",&n,&m); 35 while(m--){ 36 scanf("%d%d",&t1,&t2); 37 a[t1][t2]=a[t2][t1]=1; 38 } 39 cnt=getc(); 40 scanf("%d",&k); 41 for(int i=1;i<=k;++i){ 42 scanf("%d",&t1); 43 for(int j=0;j<n;++j) 44 a[t1][j]=a[j][t1]=0; 45 cnt1=getc(); 46 if(cnt1>cnt+1) 47 printf("Red Alert: City %d is lost!\n",t1); 48 else 49 printf("City %d is lost.\n",t1); 50 if(i==n) 51 printf("Game Over.\n"); 52 cnt=cnt1; 53 } 54 return 0; 55 }