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 =  + ;

 vector<int> E[maxn];

 int dfn[maxn], low[maxn], tot, n, ans =, vis[maxn];

 stack<int> S;

 void init() {

     for (int i = ; i < maxn; i++) vis[i] = dfn[i] = low[i] = ;

     tot = ;

     ans = ;

 }

 void tarjan(int x) {

     low[x] = dfn[x] = ++tot;

     S.push(x); vis[x] = ;

     for (int i = ; 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 () {

             int now = S.top();

             S.pop();

             vis[x] = ;

             //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 = ; i < n; i++)E[i].push_back(i);

     for (int i = ; i <= m; i++) {

         int x, y;

         scanf("%d%d", &x, &y);//判重？？没用

         if (st[x].count(y) == ) { E[x].push_back(y); st[x].insert(y); }

         if (st[y].count(x) == ) { E[y].push_back(x); st[y].insert(x); }

         //E[y].push_back(x);

     }

     //n500m5000

     for (int i = ; i <= n; i++) {

         if (!dfn[i])tarjan(i);

     }

     int last = ans;

     int q; cin >> q;

     for (int j = ; j <= q; j++) {

         int x; cin >> x;

         int ok = ;

         for (int i = ; 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 = ; i <= n; i++) {

             if (!dfn[i])tarjan(i);

         }

         if (ans > last + ) ok = ;

         last = ans;

         if (ok)printf("Red Alert: City %d is lost!\n", x);

         else printf("City %d is lost.\n", x);

     }

     //cout << ans << endl;

     if (q == n)cout << "Game Over.";

     system("pause");

 }