hdu 2460 Network (双连通分支+暴力LCA)

浏览数：46 / 时间：2015年06月09日

题意：在一张图中给出q个加边操作，问你每次操作之后图中割边的个数。点数1e5询问1000

思路：这道题的做法是先对图进行缩点，然后变成一颗树，每次添加新边若是边的两个端点属于不同的分支则一定会形成一个环，这时暴力lca标记所有换上的边有割边变为不是割边。每次统计就可以了。理论上说，每次给V字形的图复杂度会是1e8还有多组数据可能会超时，但这道题能通过。另外这道题会爆栈，注意c++扩栈。

代码如下：

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-09-01 15:25
  5  * Filename     : hdu_2460.cpp
  6  * Description     : 
  7  * ************************************************/
  8 #pragma comment(linker, "/STACK:1024000000,1024000000")
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <string>
 14 #include <cmath>
 15 #include <algorithm>
 16 #include <queue>
 17 #include <stack>
 18 #include <vector>
 19 #include <set>
 20 #include <map>
 21 #define MP(a, b) make_pair(a, b)
 22 #define PB(a) push_back(a)
 23 
 24 using namespace std;
 25 typedef long long ll;
 26 typedef pair<int, int> pii;
 27 typedef pair<unsigned int,unsigned int> puu;
 28 typedef pair<int, double> pid;
 29 typedef pair<ll, int> pli;
 30 typedef pair<int, ll> pil;
 31 
 32 const int INF = 0x3f3f3f3f;
 33 const double eps = 1E-6;
 34 const int LEN = 100010;
 35 vector<int> Map[LEN], tMap[LEN];
 36 stack<int> s;
 37 int n, m, dclock, low[LEN], dfn[LEN], block, blong[LEN];
 38 int dep[LEN], parent[LEN], is[LEN];
 39 
 40 void init()
 41 {
 42     memset(dfn, -1, sizeof dfn);
 43     memset(is, 0, sizeof is);
 44     memset(parent, 0, sizeof parent);
 45     dclock = is[1] = 1; block = 0;
 46     while(!s.empty())s.pop();
 47     for(int i=0; i<LEN; i++) Map[i].clear();
 48 }
 49 
 50 void dfs(int u, int fa){
 51     int v, flag = 0;
 52     dfn[u] = low[u] = dclock++;
 53     s.push(u);
 54     for(int i=0; i<Map[u].size(); i++){
 55         v = Map[u][i];
 56         if(v==fa && !flag){flag = 1;continue;}
 57         if(dfn[v]<0){
 58             dfs(v, u);
 59             low[u] = min(low[u], low[v]);
 60         }else if(low[u]>low[v]) low[u] = min(low[u], dfn[v]);
 61     }
 62     if(low[u] == dfn[u]){
 63         block ++;
 64         do{
 65             v = s.top(); s.pop();
 66             blong[v] = block;
 67         }while(v!=u);
 68     }
 69 }
 70 
 71 void DFS(int v, int fa, int d){
 72     dep[v] = d;
 73     parent[v] = fa;
 74     for(int i=0; i<tMap[v].size(); i++){
 75         int x = tMap[v][i];
 76         if(x != fa)    DFS(x, v, d+1);
 77     }
 78 }
 79 
 80 void build(){
 81     int a, b;
 82     map<pii, int> mp; mp.clear();
 83     for(int i=0; i<LEN; i++) tMap[i].clear();
 84     for(int i=0; i<n; i++)
 85         for(int j=0; j<Map[i].size(); j++){
 86             int x = Map[i][j];
 87             if(blong[i] == blong[x]) continue;
 88             a = blong[i], b = blong[x];
 89             if(mp.count(MP(a, b))) continue;
 90             mp[MP(a, b)] = mp[MP(b, a)] = 1;
 91             tMap[a].PB(b); tMap[b].PB(a);
 92         }
 93     DFS(1, 0, 0);
 94 }
 95 
 96 void _(int val) {cout << "\"" << val << endl;}
 97 
 98 
 99 void lca(int a, int b){
100     if(dep[a] < dep[b]) swap(a, b);
101     int tmp = dep[a] - dep[b];
102     for(int i=0; i<tmp; i++) {
103         if(!is[a]) {is[a] = 1;block --;}
104         a = parent[a];
105     }
106     while(a != b) {
107         if(!is[a]) {is[a] = 1; block --;}
108         if(!is[b]) {is[b] = 1; block --;}
109         a = parent[a], b = parent[b];
110     }
111 }
112 
113 int main()
114 {
115 //    freopen("in.txt", "r", stdin);
116 
117     int a, b, q, kase = 1;
118     while(scanf("%d%d", &n, &m) != EOF){
119         if(!n && !m) break;
120         init();
121         for(int i=0; i<m; i++){
122             scanf("%d%d", &a, &b);
123             a--, b--;
124             Map[a].PB(b); Map[b].PB(a);
125         }
126         dfs(0, -1);
127         build();
128         scanf("%d", &q);
129         printf("Case %d:\n", kase ++);
130         for(int i=0; i<q; i++){
131             scanf("%d%d", &a, &b);
132             a--; b--;
133             if(blong[a] != blong[b]) lca(blong[a], blong[b]);
134             printf("%d\n", block - 1);
135         }
136         puts("");
137     }
138     return 0;
139 }