POJ3694 Network(连通图+LCA)

题目链接:http://poj.org/problem?id=3694

题目大意:给定一个图,每次添加一条边(可能有重边)。输出每次添加后桥的

数目。由于添加边的次数比较多,添加一次Tarjin一次明显会超时。后来查到了

LCA算法,利用保存的子节点与最近父节点的关系进行计算的。第一次Tarjin后将

桥和其所在的父子节点关系保存下来,之后的m次添加边只需要在LCA中判断添加

的边是否为桥,若为桥则将此桥标记抹去,并将桥数减一,否则无影响。

附AC代码:

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct ad
{
int to, next, used;
}edge[];
int head[], edge_num, dfn[], low[], bridge_num, Time, father[];
bool isbridge[];
void Add(int x, int y)
{
edge[edge_num].to = y;
edge[edge_num].next = head[x];
edge[edge_num].used = ;
head[x] = edge_num++;
}
void Init()
{
memset(head, -, sizeof(head));
memset(father, , sizeof(father));
memset(low, , sizeof(low));
memset(dfn, , sizeof(dfn));
memset(isbridge, false, sizeof(isbridge));
edge_num = Time = bridge_num = ;
}
void Tarjin(int u, int fa)
{
father[u] = fa;
low[u] = dfn[u] = ++Time;
int i, v;
for(i=head[u]; i!=-; i=edge[i].next)
{
if(edge[i].used==)
{
edge[i].used = edge[i^].used = ;
v = edge[i].to;
if(!dfn[v])
{
Tarjin(v, u);
low[u] = min(low[u], low[v]);
if(low[v]>dfn[u])
{
bridge_num++;
isbridge[v] = true;
}
}
else if(v!=fa)
low[u] = min(low[u], dfn[v]);
}
}
}
void LCA(int u, int v)
{
if(dfn[u]>dfn[v])
swap(u, v);
while(dfn[v]>dfn[u])
{
if(isbridge[v])bridge_num--;
isbridge[v] = false;
v = father[v];
} while(u!=v)
{
if(isbridge[u])bridge_num--;
if(isbridge[v])bridge_num--;
isbridge[u] = isbridge[v] = false;
u = father[u];
v = father[v];
}
}
int main()
{
int n, m, icase = ;
while(scanf("%d %d", &n, &m), n+m)
{
int a, b;
Init();
for(int i=; i<=m; i++)
{
scanf("%d %d", &a, &b);
Add(a, b);
Add(b, a);
}
Tarjin(, -);
int Q;
scanf("%d", &Q);
printf("Case %d:\n", icase++);
while(Q--)
{
scanf("%d %d", &a, &b);
LCA(a, b);
printf("%d\n", bridge_num);
}
}
return ;
}
上一篇:Spring.net 学习


下一篇:MVC+EF 随笔小计——分部视图(Partial View)及Html.Partial和Html.Action差异