小天给大家谈谈tarjan算法，以及tarjan算法证明应用的知识点，希望对你所遇到的问题有所帮助。

1、不知道对不对，强连通图忘了，#include#includeusing namespace std;#define N 105int map[N][N],in[N],out[N],dfn[N],low[N],belong[N];int instack[N],scc,index,n;stackS;void tarjan(int x){int i,v;dfn[x]=low[x]=index;index++;S.push(x);instack[x]=1;for(i=0;i{if(map[x][i]==0)continue;if(dfn[i]==-1){tarjan(&i);low[x]=low[x]>low[i]?low[i]:low[x];}else if(instack[i])low[x]=low[x]>dfn[i]?dfn[i]:low[x];}if(low[x]==dfn[x]){while(1){}scc++;}}int main(){int i,j,n,ind,outd;while(scanf("%d",&n)!=EOF){scc=index=0;memset(map,0,sizeof(map));memset(dfn,-1,sizeof(dfn));memset(instack,0,sizeof(instack));for(i=0;i{scanf("%d",&j);while(j!=0){map[i][j-1]=1;scanf("%d",&j);}}for(i=0;iif(dfn[i]==-1)tarjan(&i);ind=outd=0;memset(in,0,sizeof(in));memset(out,0,sizeof(out));for(i=0;ifor(j=0;jif(map[i][j] && belong[i]!=belong[j]){in[belong[j]]++;out[belong[i]]++;}for(i=0;i{if(in[i]==0)ind++;if(out[i]==0)outd++;}if(scc==1)printf("1n0n");elseprintf("%dn%dn",ind,ind>outd?ind:outd);}return 0;}。

本文到这结束，希望上面文章对大家有所帮助。