poj 3694 Network

本文从WordPress迁移而来, 查看全部WordPress迁移文章

连通分量+LCA

题意:一个无向图可以有重边,下面q个操作,每次在两个点间连接一条有向边,每次连接后整个无向图还剩下多少桥(注意是要考虑之前连了的边,每次回答是在上一次的基础之上)

首先运行一次tarjan,求出桥和缩点,那么远无向图将缩点为一棵树,树边正好是原来的桥。每次连接两点,看看这两点是不是在同一个缩点内,如果是,那么缩点后的树没任何变化,如果两点属于不同的缩点,那么连接起来,然后找这两个缩点的LCA,,因为从点u到LCA再到点v再到点u,将形成环,里面的树边都会变成不是桥。计数的时候注意,有些树边可能之前已经被标记了,这次再经过不能再标记

首先按思路写了个代码,跑了2s多,因为显式建树了。不过如果理解好tarjan的话,其实发现不需要显式建树,可以利用tarjan留下的dfn和low的信息找LCA

另外找LCA这里用朴素的方法,因为这次找LCA是要找到路径的,而且途中有些边是被标记了的。朴素的方法就是在树中记录节点的父亲,然后沿着父亲走回根去

修改后跑了1s多一点。牛人是用并查集来缩点,能跑出200ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
using namespace std;
#define N 100010
#define M 200010

vector<int>ver[N];
int head[N],dfn[N],low[N],vis[N],fa[N],dcnt,bcnt;
struct edge{
int u,v,used,next;
}e[2*M];
bool isbridge[N];

inline void add(int u, int v ,int &k)
{
e[k].v = v; e[k].used = 0;
e[k].next = head[u]; head[u] = k++;
}

void LCA(int u,int v)
{
if(dfn[u] < dfn[v]) swap(u,v);
while(dfn[u] > dfn[v])
{
if(isbridge[u]) bcnt--;
isbridge[u] = false;
u = fa[u];
}
while(u!=v)
{
if(isbridge[u]) bcnt--;
if(isbridge[v]) bcnt--;
isbridge[u] = isbridge[v] = false;
u = fa[u]; v = fa[v];
}
}

void dfs(int u)
{
vis[u] = 1; dfn[u] = low[u] = ++dcnt;
for(int k=head[u]; k!=-1; k=e[k].next)
if(!e[k].used)
{
e[k].used = e[k^1].used = 1;
int v = e[k].v;
if(!vis[v])
{
fa[v] = u;
dfs(v);
low[u] = min(low[u] , low[v]);
if(dfn[u] < low[v])
{ bcnt++; isbridge[v] = true; }
}
else if(vis[v] == 1) low[u] = min(low[u],dfn[v]);
}
vis[u] = 2;
}

int main()
{
int n,m,q,cas=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n && !m) break;
memset(head,-1,sizeof(head));
int k = 0;
for(int i=0; i<m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v,k);
add(v,u,k);
}
memset(isbridge,false,sizeof(isbridge));
memset(vis,0,sizeof(vis));
dcnt = bcnt = 0;
fa[1] = 1;
dfs(1);
printf("Case %d:\n",++cas);
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
LCA(u,v);
printf("%d\n",bcnt);
}
printf("\n");
}
return 0;
}