hdu 2460

时间:2023-03-09 01:22:15
hdu 2460

这是一道双联通分量的题,要用到LCA算法;

听说这个算法有两种实现方式:一个是dfs+线段树或着RMQ;一个是用tarjin;

我用的是tarjin;

题目比较简单,就是每次加了一条边之后剩下的桥的个数;

代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100009
#pragma comment(linker,"/STACk:10240000,10240000") int n,m,cnt,NE,BridgeNum;
int parent[MAXN],low[MAXN],dfn[MAXN];
bool mark[MAXN],isbridge[MAXN];
vector<int>ve[MAXN]; void Tarjan(int u,int father)
{
int flag=;
low[u]=dfn[u]=++cnt;
mark[u]=true;
int l=ve[u].size();
for(int i=; i<l; i++)
{
int v=ve[u][i];
if(v==father&&!flag)
{
flag=;
continue;
}
if(dfn[v]==)
{
parent[v]=u;
Tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
isbridge[v]=;
BridgeNum++;
}
}
else if(mark[v])
low[u]=min(low[u],dfn[v]);
}
} void LCA(int u,int v)
{
while(dfn[u]>dfn[v])
{
if(isbridge[u])
{
BridgeNum--;
isbridge[u]=;
}
u=parent[u];
}
while(dfn[v]>dfn[u])
{
if(isbridge[v])
{
BridgeNum--;
isbridge[v]=;
}
v=parent[v];
}
while(u!=v)
{
if(isbridge[u])
{
BridgeNum--;
isbridge[u]=;
}
if(isbridge[v])
{
BridgeNum--;
isbridge[v]=;
}
u=parent[u],v=parent[v];
}
}
int main()
{
int u,v,Q,ca=;
while(scanf("%d%d",&n,&m)&&(n+m))
{
BridgeNum=NE=cnt=;
for(int i=; i<=n; i++)
ve[i].clear();
while(m--)
{
scanf("%d%d",&u,&v);
ve[u].push_back(v);
ve[v].push_back(u);
}
memset(isbridge,,sizeof isbridge);
memset(dfn,,sizeof dfn);
memset(mark,,sizeof mark);
for(int i=; i<=n+; i++)parent[i]=i;
Tarjan(,-);
printf("Case %d:\n",ca++);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&u,&v);
LCA(u,v);
printf("%d\n",BridgeNum);
}
printf("\n");
}
return ;
}