POJ 3694 Network(Bridges and LCA)
Description
给出可能含有重边的无向图，求桥的初始数目。Q次添边，每次输出添边后桥的数目。题目保证初始时刻图是连通的。
Analyze
1.将图进行正宗缩点（新点+新边的那种）形成树
2.这棵树的每条边都是桥，在点u点v间添一条边(若u、v不在同一个连通分量中，即没缩成同一点，此举必成环），后来的桥的数目等于原来桥的数目减掉新图里这个环中(不算边u,v)边的数目。而这个数目等于u、v(对应缩点)到他们最近公共祖先LCA的距离和！这个思想绝了！原本在一般图中，要找这样一个环的边数，怕是要循环或者递归啥的，可偏偏这是在一棵树里！它有这样的特点。
具体步骤：
1.Tarjan对原图求桥
2.在有桥的前提下DFS正经缩点(学到了!)
3.根据缩点建新图(添新边以连接新缩点)
4.BFS求新点的深度(层)，为求某两点距离其LCA的距离做准备
5.利用个点深度求两点距离各自LCA的距离
最后添边在LCA函数里一边查询距离，一边更新(桥变非桥)
Something
关于正宗缩点：
1.朱刘算法求最小树形图的时候，缩点并不是很正宗，点处理的很好，但是边还是用的之前的边，没添一条没删一条。当然这是算法必须具备的特点，正经缩点还不适合它的情境、它的需求。
2.并查集缩点就更不正宗了……
关于处理重边的问题：
为了不走反向边 同时 不忽略重边
if(i == pre_e_num ^ 1)continue;
Code
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
const int M = 600005;
int n, m, Q;
int cnt, tot, idx, deep[N], id[N], h1[N], h2[N], low[N], times[N], num_bridges;
bool bridge[M];
struct edge
{
int u, v, pre;
} e[M];
struct shrink_node
{
int pre, e_num;
} node[N];
void init()
{
cnt = tot = idx = num_bridges = 0;
memset(h1, -1, sizeof(h1));
memset(h2, -1, sizeof(h2));
memset(id, 0, sizeof(id));
memset(low, 0, sizeof(low));
memset(deep, 0, sizeof(deep));
memset(times, 0, sizeof(times));
memset(bridge, 0, sizeof(bridge));
}
void add(int u, int v, int head[])
{
e[cnt].u = u;
e[cnt].v = v;
e[cnt].pre = head[u];
head[u] = cnt++;
}
void Tarjan(int x, int pre_e_num)///Get all bridges!
{
low[x] = times[x] = ++tot;
for(int i = h1[x]; ~i; i = e[i].pre)
{
int to = e[i].v;
if(i == (pre_e_num ^ 1))///Deal with repeated edges!
continue;
if(!times[to])
{
Tarjan(to, i);
low[x] = min(low[x], low[to]);
if(low[to] > times[x])
{
num_bridges++;
bridge[i] = bridge[i ^ 1] = 1;
}
}
else
low[x] = min(low[x], times[to]);
}
}
void DFS(int x)///Shrink by bridges!
{
id[x] = idx;
for(int i = h1[x]; ~i; i = e[i].pre)
{
int to = e[i].v;
if(id[to] || bridge[i])///Don't go through any bridge!
continue;
DFS(to);
}
}
void BFS()///Get the deep to prepare to get the LCA!
{
deep[1] = 1, node[1].pre = 0;
queue<int> q;
q.push(1);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i = h2[now]; ~i; i = e[i].pre)
{
int to = e[i].v;
if(deep[to])
continue;
deep[to] = deep[now] + 1;
q.push(to);
node[to].pre = now;
node[to].e_num = i;
}
}
}
int LCA(int x, int y)
{
int ans = 0;
if(deep[y] >= deep[x])
swap(x, y);
while(deep[x] > deep[y])
{
if(bridge[ node[x].e_num ])///Only count the bridges!
{
ans++;
bridge[ node[x].e_num ] = bridge[ node[x].e_num ^ 1 ] = 0;
}
x = node[x].pre;
}
if(x == y)
return ans;
while(x != y)
{
int ex = node[x].e_num, ey = node[y].e_num;
if(bridge[ex])
ans++, bridge[ex] = bridge[ex ^ 1] = 0;
if(bridge[ey])
ans++, bridge[ey] = bridge[ey ^ 1] = 0;
x = node[x].pre, y = node[y].pre;
}
return ans;
}
int main()
{
int t = 1;
while(~scanf("%d %d", &n, &m) && (n + m))
{
init();
int u, v;
for(int i = 0; i < m; ++i)
{
scanf("%d %d", &u, &v);
add(u, v, h1), add(v, u, h1);
}
Tarjan(1, -1);
for(int i = 1; i <= n; ++i)
if(!id[i])
++idx, DFS(i);
int number = cnt;
for(int i = 0; i < number; i += 2)
{
u = e[i].u, v = e[i].v;
if(id[u] == id[v])
continue;
bridge[cnt] = 1;
add(id[u], id[v], h2);
bridge[cnt] = 1;
add(id[v], id[u], h2);
}
BFS();
scanf("%d", &Q);
cout << "Case " << t++ << ":\n";
while(Q--)
{
scanf("%d %d", &u, &v);
if(id[u] != id[v])
num_bridges -= LCA(id[u], id[v]);
cout << num_bridges << '\n';
}
}
return 0;
}
要想办法计算好数组大小，开小了不止会RE，还会TLE