题意:给你一个无向图,有q次操作,每次连接两个点,问你每次操作后有几个桥
思路:我们先用tarjan求出所有的桥,同时我们可以用并查集缩点,fa表示缩点后的编号,还要记录每个节点父节点pre。我们知道,缩点后形成一棵树,所有边都是桥,连接两点必会成环,环上任意边都不是桥。所以连点后,我们把两个点一步一步往上走,如果往上走之后发现fa不一样,说明走过了一条桥,那么合并fa,桥数量-1。
代码:
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
using namespace std;
int head[maxn], dfn[maxn], low[maxn], vis[maxn], fa[maxn], pre[maxn], tot, index, ans;
struct Edge{
int to, next;
}e[maxn << ];
void addEdge(int u, int v){
e[tot].to = v;
e[tot].next = head[u];
head[u] = tot++;
}
int find(int x){
return fa[x] == x? x : fa[x] = find(fa[x]);
}
void Union(int u, int v){
int fx = find(u);
int fy = find(v);
if(fx != fy){
fa[fx] = fy;
}
}
void tarjan(int u, int Fa){
vis[u] = ;
dfn[u] = low[u] = ++index;
pre[u] = Fa;
for(int i = head[u]; i != -; i = e[i].next){
int v = e[i].to;
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]){
ans++;
}
else{
Union(u, v);
}
}
else if(v != Fa){
low[u] = min(low[u], dfn[v]);
}
}
}
void Move(int x){
int fx = find(x);
int fy = find(pre[x]);
if(fx != fy){
fa[fx] = fy;
ans--;
}
}
void LCA(int u, int v){
while(dfn[u] > dfn[v]){
Move(u);
u = pre[u];
}
while(dfn[v] > dfn[u]){
Move(v);
v = pre[v];
}
while(u != v){
Move(u);
Move(v);
u = pre[u];
v = pre[v];
}
}
void init(){
tot = index = ans = ;
memset(head, -, sizeof(head));
memset(vis, , sizeof(vis));
memset(dfn, , sizeof(dfn));
}
int main(){
int n, m, Case = ;
while(scanf("%d%d", &n, &m) && n + m){
init();
int u, v;
for(int i = ; i < m; i++){
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for(int i = ; i <= n; i++)
fa[i] = i;
tarjan(, );
int q;
scanf("%d", &q);
printf("Case %d:\n", Case++);
while(q--){
scanf("%d%d", &u, &v);
if(find(u) != find(v)){
LCA(u, v);
}
printf("%d\n", ans);
}
printf("\n");
}
return ;
}