tarjan求强连通分量，task a 是入度为0的新节点，task b 是max（入度为0，出度为0），当整个图是一个强连通分量是，输出1,0
#include<iostream> using namespace std; #define N 105 typedef struct node* pointer; struct node { int ver; pointer next; }; int low[N],ord[N],id[N],stk[N],cnt,scnt; bool instk[N],map1[N],map2[N]; pointer g[N]; void insert(int u,int v) { pointer ptr=new node; ptr->ver=v; ptr->next=g[u]; g[u]=ptr; } int mymax(int a,int b) { if(a>b) return a; else return b; } void tarjan(int e) { int t; pointer ptr; low[e]=++cnt; ord[e]=cnt; stk[++stk[0]]=e; instk[e]=true; ptr=g[e]; while(ptr!=NULL) { t=ptr->ver; if(!ord[t]) { tarjan(t); if(low[e]>low[t]) low[e]=low[t]; } else if(instk[t]&&low[e]>ord[t]) low[e]=ord[t]; ptr=ptr->next; } if(low[e]==ord[e]) { scnt++; do { t=stk[stk[0]--]; id[t]=scnt; instk[t]=false; }while(t!=e); } return ; } void find_component(int n) { int i; memset(instk,false,sizeof(instk)); memset(ord,0,sizeof(ord)); cnt=0,scnt=0,stk[0]=0; for(i=1;i<=n;i++) if(!ord[i]) tarjan(i); return ; } int main() { int n,i,x,flag1,flag2,t; pointer ptr; scanf("%d",&n); for(i=1;i<=n;i++) g[i]=NULL; for(i=1;i<=n;i++) { while(scanf("%d",&x),x) insert(i,x); } find_component(n); if(scnt==1) { printf("1/n0/n"); return 0; } memset(map1,0,sizeof(map1)); memset(map2,0,sizeof(map2)); flag1=0,flag2=0; for(i=1;i<=n;i++) { ptr=g[i]; while(ptr!=NULL) { t=ptr->ver; if(id[i]!=id[t]) { map1[id[i]]=1; map2[id[t]]=1; } ptr=ptr->next; } } for(i=1;i<=scnt;i++) { if(!map1[i]) flag1++; if(!map2[i]) flag2++; } printf("%d/n%d/n",flag2,mymax(flag1,flag2)); return 0; }
