本文主要是介绍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<stdio.h>
#include<string.h>
#include<algorithm>
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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
