Game Over.
解题思路:
用填充法去dfs判断连通分量个数,每失去城市都去求一次,如果这一次的连通分量比上一次少了,那么就输出红色警报。
记住一定要 和上一次连通分量个数比较,那么每次的连通分量不管是比上次增加了还是减少了都要记录一下。
代码:
#include <bits/stdc++.h> using namespace std; const double eps=1e-4; const int maxn=600; int a[maxn][maxn]; int n,m; int book[maxn]; int top; void dfs(int x) { int xx, yy, i, j; book[x]=top; // printf("%d\n", x); for(i=0; i<n; i++) { if(book[i]==0 && a[x][i]) { dfs(i); } } return; } int main() { cin>>n>>m; int x, y, i, j; for(i=0; i<m; i++) { scanf("%d%d", &x, &y); a[x][y]=a[y][x]=1; } int k; cin>>k; top=0; for(j=0; j<n; j++) { if(book[j]==0) { ++top; dfs(j); } } int num=top; memset(book, 0, sizeof(book)); for(i=0; i<k; i++) { scanf("%d", &x); book[x]=-1; for(int i=0; i<n; i++)a[x][i]=a[i][x]=0; top=0; for(j=0; j<n; j++) { if(book[j]==0) { ++top; dfs(j); } } if(num<top) { printf("Red Alert: City %d is lost!\n", x); } else printf("City %d is lost.\n", x); num=top; //记录上一次的连通分量 for(int i=0; i<n; i++){if(book[i]>0)book[i]=0;}; //将还没被进攻的访问过的城市初始化 } if(i==n){printf("Game Over.\n");} return 0; }