nyoj 120 建边构强连通
阅读原文时间:2023年07月08日阅读:2

#include
#include
#include
using namespace std;
#define N 200

struct node
{
int u,v,next;
} bian[N*N];
int n,dfn[N],low[N],stac[N],yong,head[N],visit[N],ans,top,inde,suo[N],indegree[N],outdegree[N];
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(stac,0,sizeof(stac));
memset(visit,0,sizeof(visit));
memset(suo,0,sizeof(suo));
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
ans=0;
yong=0;
top=0;
inde=0;
}
void addedge(int u,int v)
{
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
int Max(int a,int b)
{
return a>b?a:b;
}
int Min(int a,int b)
{
return a>b?b:a;
}
void tarjan(int u)
{
dfn[u]=low[u]=++inde;
stac[++top]=u;
visit[u]=1;
int i;
for(i=head[u]; i!=-1; i=bian[i].next)
{
if(!dfn[bian[i].v])
{
tarjan(bian[i].v);
low[u]=Min(low[u],low[bian[i].v]);
}
else if(visit[bian[i].v]==1)
low[u]=Min(low[u],dfn[bian[i].v]);

}  
if(dfn\[u\]==low\[u\])  
{  
    ans++;  
    int t;  
    do  
    {  
        t=stac\[top--\];  
        visit\[t\]=2;  
        suo\[t\]=ans;  
    }  
    while(t!=u);  
}  

}
int main()
{
int t,n,m,i,fin,fout;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(i=1; i<=n; i++)
{
while(scanf("%d",&m),m)
addedge(i,m);
}
for(i=1; i<=n; i++)
if(visit[i]!=2)
tarjan(i);
if(ans==1) {//important
printf("0\n");
continue;
}
for(i=0;i<yong;i++)
if(suo[bian[i].u]!=suo[bian[i].v]) {
indegree[suo[bian[i].u]]++;
outdegree[suo[bian[i].v]]++;
}
fin=0;
fout=0;
for(i=1; i<=ans; i++)
{
if(indegree[i]==0)
fin++;
if(outdegree[i]==0)
fout++;
}
printf("%d\n",Max(fin,fout));
}

return 0;  

}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章