首页 > 代码库 > 最近切的两题SCC的tarjan POJ1236 POJ2186
最近切的两题SCC的tarjan POJ1236 POJ2186
两题都是水题，1236第一问求缩点后入度为0的点数，第二问即至少添加多少条边使全图强连通，属于经典做法，具体可以看白书
POJ2186即求缩点后出度为0的那个唯一的点所包含的点数（即SCC里有多少点）
//poj1236
#include<iostream>
#include<cstdio>
#include<string.h>
#define maxn 6000
int now=0,next[maxn],head[maxn],point[maxn],num=0,dfn[maxn],low[maxn],instack[maxn];
int stack[maxn],belong[maxn],top,count,in[maxn],out[maxn];
int min(int a,int b)
{if (a<b)return a;else return b;
}
int max(int a,int b)
{if (a>b)return a;else return b;
}
void add(int x,int y)
{next[++now]=head[x];
head[x]=now;
point[now]=y;
}
void tarjan(int k)
{int u;
instack[k]=true;
dfn[k]=low[k]=++num;stack[++top]=k;
for(int i=head[k];i!=0;i=next[i])
{u=point[i];
if (dfn[u]==0)
{tarjan(u);
low[k]=min(low[k],low[u]);
}
else if (instack[u])low[k]=min(dfn[u],low[k]);
}
if (low[k]==dfn[k])
{++count;
do
{u=stack[top--];
instack[u]=false;
belong[u]=count;
}while(u!=k);
}
}
int main()
{int n,t;
scanf("%d",&n);for(int i=1;i<=n;i++)while (1)
{ scanf("%d",&t);if (t==0)break;
else add(i,t);
}
for(int i=1;i<=n;i++)if (dfn[i]==0)tarjan(i);
for(int i=1;i<=n;i++)
{for(int j=head[i];j!=0;j=next[j])
{int u=point[j];
if (belong[i]!=belong[u])
{out[belong[i]]++;
in[belong[u]]++;
}
}
}
int countout=0,countin=0;
for(int i=1;i<=count;i++)
{if (out[i]==0)countout++;
if (in[i]==0)countin++;
}
if (count==1)printf("1\n0\n"); else printf("%d\n%d\n",countin,max(countout,countin));return 0;
}
//poj2186
#include<iostream>
#include<cstdio>
#include<string.h>
#define maxn 50010
using namespace std;
intnow=0,next[maxn],head[maxn],point[maxn],num=0,dfn[maxn],low[maxn],instack[maxn];
int stack[maxn],belong[maxn],top,count,out[maxn],p[maxn];
void add(int x,int y)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
}
void tarjan(int k)
{
instack[k]=1;
stack[++top]=k;
low[k]=dfn[k]=++num;
int u;
for(inti=head[k];i!=0;i=next[i])
{
u=point[i];
if (dfn[u]==0)
{
tarjan(u);
low[k]=min(low[u],low[k]);
}
else if (instack[u]==1)low[k]=min(dfn[u],low[k]);
}
if (low[k]==dfn[k])
{
++count;
do
{
u=stack[top--];
instack[u]=0;
belong[u]=count;
p[count]++;
}while(u!=k);
}
}
int main()
{
int n,m,x,y,ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if (dfn[i]==0)tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=head[i];j!=0;j=next[j])
{
int u=point[j];
if(belong[i]!=belong[u])out[belong[i]]++;
}
}
int flag=0;
for(inti=1;i<=count;i++)
{
if (ans!=0 &&out[i]==0){flag=1;break;}
if(out[i]==0)ans=p[i];
}
if(flag==0)printf("%d\n",ans);else printf("0\n");
return 0;
}
最近切的两题SCC的tarjan POJ1236 POJ2186