poj 3352 Road Construction(边双连通分量+缩点)

时间:2023-12-23 16:30:14

题目链接:http://poj.org/problem?id=3352

这题和poj 3177 一样,参考http://www.cnblogs.com/frog112111/p/3367039.html

AC代码:

 #include<cstdio>
#include<cstring>
const int N=+;
const int M=+; struct EDGE
{
int v,next;
}edge[M*];
int first[N],low[N],dfn[N],belong[N],degree[N],sta[M],instack[M];
int g,cnt,top,scc;
int min(int a,int b)
{
return a<b?a:b;
}
void AddEdge(int u,int v)
{
edge[g].v=v;
edge[g].next=first[u];
first[u]=g++;
}
void Tarjan(int u,int fa)
{
int i,v;
low[u]=dfn[u]=++cnt;
sta[++top]=u;
instack[u]=;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(i==(fa^))
continue;
if(!dfn[v])
{
Tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
scc++;
while()
{
v=sta[top--];
instack[v]=;
belong[v]=scc;
if(v==u)
break;
}
}
}
int main()
{
int n,m,u,v,i,j;
scanf("%d%d",&n,&m);
g=cnt=top=scc=;
memset(first,-,sizeof(first));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(instack,,sizeof(instack));
memset(degree,,sizeof(degree));
for(i=;i<m;i++)
{
scanf("%d%d",&u,&v);
{
AddEdge(u,v);
AddEdge(v,u);
}
}
for(i=;i<=n;i++)
if(!dfn[i])
Tarjan(,-);
for(i=;i<=n;i++)
{
for(j=first[i];j!=-;j=edge[j].next)
{
v=edge[j].v;
if(belong[i]!=belong[v])
degree[belong[i]]++;
}
}
int sum=;
for(i=;i<=n;i++)
if(degree[i]==)
sum++;
int ans=(sum+)/;
printf("%d\n",ans);
return ;
}