CCCC L2-013. 红色警报 连通分量

题解：将问题转化成连通分量。每次失去一座城市，切断其所有的边，算一次现在的连通分量。若增量大于1，则发出警报。

　　　　至于如何算连通分量，直接用tarjan模板

坑：//我昨天晚上半夜敲的模板，把一个算所有环中最短环的tarjan模板 直接贴上去了，一直不过，还XJB改了会儿233（现在90行的代码逛逛B站随便改改就ac了2333）

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> 
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<string.h>
#include<set>
using namespace std;
const int maxn = 500 + 5;
vector<int> E[maxn];
int dfn[maxn], low[maxn], tot, n, ans =0, vis[maxn];
stack<int> S;
void init() {
    for (int i = 0; i < maxn; i++) vis[i] = dfn[i] = low[i] = 0;
    tot = 0;
    ans = 0;
}
void tarjan(int x) {
    low[x] = dfn[x] = ++tot;
    S.push(x); vis[x] = 1;
    for (int i = 0; i < E[x].size(); i++) {
        int v = E[x][i];
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);

        }
        else if (vis[x]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (low[x] == dfn[x]) {
        //int cnt = 0;
        while (1) {
            int now = S.top();
            S.pop();
            vis[x] = 0;
            //cnt++;
            if (now == x)break;
        }
        ans++;
        //if (cnt > 1)ans = min(ans, cnt);
    }
}
set<int> st[maxn];
int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)E[i].push_back(i);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);//判重？？没用
        if (st[x].count(y) == 0) { E[x].push_back(y); st[x].insert(y); }
        if (st[y].count(x) == 0) { E[y].push_back(x); st[y].insert(x); }
        //E[y].push_back(x);
    }
    //n500m5000
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])tarjan(i);
    }
    int last = ans;
    int q; cin >> q;
    
    for (int j = 1; j <= q; j++) {
        int x; cin >> x;
        int ok = 0;
        for (int i = 0; i < E[x].size(); i++) {
            int v = E[x][i];
//            for (auto t : E[v]) if (t == x)t = -1;//强行去除反向边。
            for (vector<int>::iterator it = E[v].begin(); it != E[v].end(); it++)if (*it == x) { E[v].erase(it); break; }
        }

        E[x].clear();
        E[x].push_back(x);
        init();
        //cout << last<< endl;
        for (int i = 1; i <= n; i++) {
            if (!dfn[i])tarjan(i);
        }
        if (ans > last + 1) ok = 1;
        last = ans;
        if (ok)printf("Red Alert: City %d is lost!
", x);
        else printf("City %d is lost.
", x);
    }
    //cout << ans << endl;
    if (q == n)cout << "Game Over.";
    system("pause");
}