题目链接
https://www.patest.cn/contests/gplt/L2-013
思路
可以通过图的连通块个数来判断
假如 一座城市的失去 改变了其他城市之间的连通性
那么 这座城市本来所在的连通块 就会被分裂成为 两个以上的连通块
加上 这座城市 被分裂出来 又多了 一个连通块
所以 在每次失去的时候 我们深搜 判断一下 连通块个数
如果 失去后的连通块个数 > 原来连通块个数 + 1 那么 就要发出红色警报了
要记得 每次更新一下 连通块 个数
每次都要更新 保证每次判断 都是在上一次失去的基础上 判断的
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 5e2 + 5; const int MOD = 1e9 + 7; int G[maxn][maxn]; int v[maxn]; int n, m; void dfs(int x) { v[x] = 1; for (int i = 0; i < n; i++) { if (v[i] == 0 && G[x][i] == 1) dfs(i); } } void init() { CLR(G); CLR(v); } int main() { scanf("%d%d", &n, &m); int x, y; for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); G[x][y] = G[y][x] = 1; } int fin = 0; for (int i = 0; i < n; i++) { if (v[i] == 0) { dfs(i); fin++; } } int k; scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%d", &x); for (int j = 0; j < n; j++) G[x][j] = G[j][x] = 0; int temp = 0; CLR(v); for (int j = 0; j < n; j++) { if (v[j] == 0) { dfs(j); temp++; } } if (temp > fin + 1) printf("Red Alert: City %d is lost!\n", x); else printf("City %d is lost.\n", x); fin = temp; if (i == n - 1) printf("Game Over.\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433176.html
