第一次写，写出Ⅹ了，顺带一篇大佬博客，但建议一边做题一边看，不然不好看懂http://blog.csdn.net/jeryjeryjery/article/details/52829142?locationNum=4&fps=1
#include <iostream> #include <cstdio> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <set> using namespace std; #define hh printf("--------------\n"); const int maxn=100+10; vector<int> g[maxn]; int ncnt,ccnt;//点数量，连通分支数量 bool vis[maxn],insk[maxn]; int low[maxn],dfn[maxn];//最小祖先，点的标号 int noc[maxn];//点指向的连通分支 stack<int> sk; int n; void tarjan(int x) { ncnt++;//点标号计数 vis[x]=1; insk[x]=1; low[x]=ncnt; dfn[x]=ncnt; sk.push(x); for(int i=0;i<g[x].size();i++) { int v=g[x][i]; if(!vis[v]) { tarjan(v); low[x]=min(low[x],low[v]);//更新祖先 } else if(insk[v])//如果已检测，且在栈里，则可构成环 { low[x]=min(low[x],dfn[v]);//寻找最小祖先，也就是开始画环的开始点 } } if(low[x]==dfn[x])//弹出一个强连通分支，就是一个环，如果不能构成环，则弹出的是它自身 { int v; //有环只有找到它的祖先才能进行 do { v=sk.top(); sk.pop(); noc[v]=ccnt; insk[v]=0; } while(v!=x);//直到栈内的点不在环内，也就是弹出的最后一个点是它自己，而不是它的祖先 ccnt++;//连通分支数 } } //set防止重复 vector<set<int> > linefrom; vector<set<int> > lineto; void yasuo(int nn,int nc)//将环压缩成点 { linefrom.resize(nc); lineto.resize(nc); for(int i=1;i<=nn;i++) for(int j=0;j<g[i].size();j++) { int u=i; int v=g[i][j]; int cu=noc[u]; int cv=noc[v]; if(cv!=cu)//不在同一个环内 { linefrom[cv].insert(cu);//可以从u到v lineto[cu].insert(cv); } } } void init() { ncnt=0; ccnt=0; for(int i=0;i<=n;i++) g[i].clear(); memset(vis,0,sizeof(vis)); memset(insk,0,sizeof(insk)); memset(noc,0,sizeof(noc)); while(sk.size()) sk.pop(); linefrom.clear(); lineto.clear(); } int main() { while(~scanf("%d",&n)) { int a; init(); for(int i=1;i<=n;i++) { while(scanf("%d",&a)&&a!=0) g[i].push_back(a); } for(int i=1;i<=n;i++) if(!vis[i]) { tarjan(i); } yasuo(n,ccnt); int z_in=0,z_out=0; for(int i=0;i<ccnt;i++) { if(linefrom[i].empty()) z_in++;//入度为0的点的个数 if(lineto[i].empty()) z_out++;//出度为0的点的个数 } if(ccnt==1) printf("1\n0\n"); else { printf("%d\n%d\n",z_in,max(z_in,z_out)); } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7511145.html
