[題目連結]
http://poj.org/problem?id=3694
[算法]
首先，我們用tarjan算法求出所有的邊雙聯通分量，然後，将這張圖縮點
如果添加的邊(x,y)在同一個雙聯通分量中，答案不變，否則，給belong[x]-belong[y]的路徑上的邊作标記，可以用并查集加速這個過程
[代碼]
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 100010
#define MAXM 200010
#define MAXLOG 20
struct edge
{
int to,nxt;
} e[MAXM << 2],ec[MAXM << 2];
int i,j,n,m,ans,tot,ctot,cnt,u,v,timer,Lca,x,y,q,TC;
int head[MAXN],chead[MAXN],low[MAXN],dfn[MAXN],belong[MAXN],fa[MAXN],depth[MAXN];
int anc[MAXN][MAXLOG];
bool is_bridge[MAXM << 1],visited[MAXN];
inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline void addcedge(int u,int v)
{
ctot++;
ec[ctot] = (edge){v,chead[u]};
chead[u] = ctot;
}
inline void tarjan(int u,int t)
{
int i,v;
dfn[u] = low[u] = ++timer;
visited[u] = true;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
tarjan(v,i);
if (low[v] > dfn[u]) is_bridge[i] = is_bridge[i ^ 1] = true;
low[u] = min(low[u],low[v]);
} else if (i != (t ^ 1)) low[u] = min(low[u],dfn[v]);
}
}
inline void dfs(int u)
{
int i,v;
belong[u] = cnt;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (belong[v] || is_bridge[i]) continue;
dfs(v);
}
}
inline void lca_init()
{
int i,j,u,v;
queue< int > q;
while (!q.empty()) q.pop();
q.push(1);
depth[1] = 1;
while (!q.empty())
{
u = q.front();
q.pop();
for (i = chead[u]; i; i = ec[i].nxt)
{
v = ec[i].to;
if (depth[v]) continue;
depth[v] = depth[u] + 1;
anc[v][0] = u;
for (j = 1; j < MAXLOG; j++)
anc[v][j] = anc[anc[v][j - 1]][j - 1];
q.push(v);
}
}
}
inline int lca(int x,int y)
{
int i,t;
if (depth[x] > depth[y]) swap(x,y);
t = depth[y] - depth[x];
for (i = 0; i < MAXLOG; i++)
{
if (t & (1 << i))
y = anc[y][i];
}
if (x == y) return x;
for (i = MAXLOG - 1; i >= 0; i--)
{
if (anc[x][i] != anc[y][i])
{
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
inline int get_root(int x)
{
if (fa[x] == x) return x;
return fa[x] = get_root(fa[x]);
}
int main()
{
while (scanf("%d%d",&n,&m) && (n || m))
{
tot = 1;
ctot = cnt = timer = 0;
for (i = 1; i <= n; i++)
{
head[i] = 0;
chead[i] = 0;
dfn[i] = 0;
low[i] = 0;
belong[i] = 0;
visited[i] = false;
fa[i] = i;
depth[i] = 0;
}
for (i = 1; i <= 2 * m + 1; i++) is_bridge[i] = false;
for (i = 1; i <= m; i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for (i = 1; i <= n; i++)
{
if (!dfn[i])
tarjan(i,0);
}
for (i = 1; i <= n; i++)
{
if (!belong[i])
{
cnt++;
dfs(i);
}
}
for (u = 1; u <= n; u++)
{
for (j = head[u]; j; j = e[j].nxt)
{
v = e[j].to;
if (belong[u] != belong[v])
{
addcedge(belong[u],belong[v]);
addcedge(belong[v],belong[u]);
}
}
}
ans = cnt - 1;
lca_init();
printf("Case %d:\n",++TC);
scanf("%d",&q);
while (q--)
{
scanf("%d%d",&u,&v);
x = belong[u]; y = belong[v];
Lca = lca(x,y);
x = get_root(x);
while (depth[x] > depth[Lca])
{
fa[x] = anc[x][0];
ans--;
x = get_root(x);
}
y = get_root(y);
while (depth[y] > depth[Lca])
{
fa[y] = anc[y][0];
ans--;
y = get_root(y);
}
printf("%d\n",ans);
}
printf("\n");
}
return 0;
} 轉載于:https://www.cnblogs.com/evenbao/p/9397244.html