int n, m; int f[MAX_SIZE];//并查集数组 Line lines[MAX_SIZE]; bool lost_flag[MAX_SIZE];//标记城市是否被攻占
intmy_query(constint &i){ return f[i] = f[i] == i ? i : my_query(f[i]); }
voidmy_merge(constint &l, constint &r){ int a = my_query(l); int b = my_query(r); f[b] = a; }
inlineintcount_part(){ int ret = 0; for (int i = 0; i < n; i++) { if (!lost_flag[i]) { f[i] = my_query(f[i]); if (f[i] == i) { ret++; } } } return ret; }
inlinevoidinf(){//初始化并查集 for (int i = 0; i < n; i++) { if (!lost_flag[i]) { f[i] = i; } } }
intmain(){ scanf("%d %d", &n, &m); inf();//初始化并查集 for (int i = 1; i <= m; i++) { scanf("%d %d", &lines[i].p1, &lines[i].p2); my_merge(lines[i].p1, lines[i].p2); } int k; scanf("%d", &k); for (int i = 1; i <= k; i++) { int t1 = count_part();//当前连通分支 int id; scanf("%d", &id); lost_flag[id] = true; inf();//初始化并查集 for (int j = 1; j <= m; j++) { if (!lost_flag[lines[j].p1] && !lost_flag[lines[j].p2]) {//该边两端点城市仍存在 my_merge(lines[j].p1, lines[j].p2); } } int t2 = count_part();//失去该城市后连通分支数 if (t1 >= t2) {//连通分支可能变少,但不影响连通度,不能t1!=t2 printf("City %d is lost.\n", id); } else { printf("Red Alert: City %d is lost!\n", id); } if(i == k && k == n) { printf("Game Over.\n"); } } return0; }