poj1236/luogu2746 Network of Schools (tarjan)

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long int 5 using namespace std; 6 const int maxn=110,maxm=10010; 7 ?8 LL rd(){ 9 ????LL x=0;char c=getchar();int neg=1;10 ????while(c<‘0‘||c>‘9‘){if(c==‘-‘) neg=-1;c=getchar();}11 ????while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar();12 ????return x*neg;13 }14 15 int N;16 int eg[maxm][2],egh[maxn],ect,bel[maxn];17 int dfn[maxn],low[maxn],stk[maxn],tot,pct,sct;18 int tin,tout;19 bool instk[maxn],in[maxn],out[maxn];20 21 void tarjan(int x){22 ????dfn[x]=low[x]=++tot;stk[++sct]=x;instk[x]=1;23 ????for(int i=egh[x];i!=-1;i=eg[i][1]){24 ????????int j=eg[i][0];25 ????????if(instk[j]) low[x]=min(low[x],dfn[j]);26 ????????else if(!dfn[j]){27 ????????????tarjan(j);low[x]=min(low[x],low[j]);28 ????????}29 ????}30 ????if(dfn[x]==low[x]){31 ????????pct++;32 ????????while(sct){33 ????????????instk[stk[sct]]=0;34 ????????????bel[stk[sct]]=pct;35 ????????????if(stk[sct--]==x) break;36 ????????}37 ????}38 }39 40 inline void adeg(int a,int b){41 ????eg[ect][0]=b;eg[ect][1]=egh[a];egh[a]=ect++;42 }43 44 int main(){45 ????int i,j,k;46 ????N=rd();memset(egh,-1,sizeof(egh));47 ????for(i=1;i<=N;i++){48 ????????while(j=rd()) adeg(i,j);49 ????}50 ????for(i=1;i<=N;i++){51 ????????if(!dfn[i]) tarjan(i);52 ????}53 ????for(i=1;i<=N;i++){54 ????????for(j=egh[i];j!=-1;j=eg[j][1]){55 ????????????k=eg[j][0];56 ????????????int ii=bel[i],kk=bel[k];57 ????????????if(ii!=kk){58 ????????????????in[kk]=1;out[ii]=1;59 ????????????}60 ????????}61 ????}for(i=1;i<=pct;i++){62 ????????if(!in[i]) tin++;63 ????????if(!out[i]) tout++;64 ????}65 ????if(pct>1)printf("%d\n%d",tin,max(tin,tout));66 ????else printf("1\n0");67 ????68 }