poj 3694 Network（tarjan + LCA）图论-连通分量

http://poj.org/problem?id=3694
题意：对于一个无向连通图，问加入某条边后，图中有桥的数目。
思路：
根据tarjan算法求出初始图的桥的数目，并用数组bridge标记桥的终点，在tarjan深搜树中求出每个节点的父节点（数组father表示）以及它们的深度，用于以后迭代求LCA。

因为加入某条边后，树中就会存在环，而环中的每条边都不再是桥，这就与求LCA有关了。在进行LCA时，由于树的组成就是原图中的桥，当加入新的一条边ab后，求出ab的最近的公共祖先c，那么a b c会直接或间接的构成环，然后根据之前的bridge数组标记和father数组来确定将那些边变为普通边。

#include #include #include using namespace std; const int maxn = 500000; struct node { int v,next; }edge[maxn]; int p[maxn],cnt; int n,m; int dfn[100100],vis[100100],low[100100],father[100100]; int bridge[100100]; //标记初始图的桥的终点 int sum; //桥的数目void add(int u,int v) { edge[cnt] = (struct node){v,p[u]}; p[u] = cnt; cnt++; }void tarjan(int u,int dep) { dfn[u] = low[u] = dep; vis[u] = 1; for(int i = p[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(vis[v] == 1 && v != father[u]) low[u] = min(low[u],dfn[v]); if(vis[v] == 0) { father[v] = u; tarjan(v,dep+1); low[u] = min(low[u],low[v]); if(low[v] > dfn[u])//是桥，标记为 1 { sum++; bridge[v] = 1; } } } vis[u] = 2; } //正常迭代实现LCA，它需要一棵树或一个图中每个节点的深度和父节点 //根据已知的信息，不断的将两个节点往回迭代，直到找到了同一高度，同一个父节点。 //这个节点便是他们两点的公共祖先了，而这个过程经过的边加起来，便是我们要找的环！ void LCA(int a, int b) { while(dfn[a] > dfn[b])// 深度不同，单个节点向上攀爬，到与另一节点同一高度 { if(bridge[a]) { sum--; bridge[a] = 0; } a = father[a]; } while(dfn[b] > dfn[a]) { if(bridge[b]) { sum--; bridge[b] = 0; } b = father[b]; } while(a != b)深度相同了，同时向上攀爬，直到成了同一点 { if(bridge[a]) { sum--; bridge[a] = 0; } a = father[a]; if(bridge[b]) { sum--; bridge[b] = 0; } b = father[b]; } }int main() { int u,v,q,test = 0; int a,b; while(~scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break; memset(p,-1,sizeof(p)); memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bridge,0,sizeof(bridge)); for(int i = 1; i <= n; i++) father[i] = i; cnt = 0; for(int i = 0; i < m; i++) { scanf("%d %d",&u,&v); add(u,v); add(v,u); }sum = 0; tarjan(1,1); printf("Case %d:\n",++test); scanf("%d",&q); while(q--) { scanf("%d %d",&a,&b); LCA(a,b); printf("%d\n",sum); } printf("\n"); } return 0; }

【poj 3694 Network（tarjan + LCA）】