题目请点我 题解： 这是我的第一道强连通分量，，虽然参考了别人的代码，还是很有收获。强连通分量的查找和处理是很多图论题目的第一步，所以还是很重要，这道题只是有向图的强连通处理。 这道题因为题目有讲每组关系都是不小于，那么如果出现环的话那只有一种情况，就是环上所有人都是相等的年龄，则这个环上所有的人的比较关系都是可以等价的，这就是为什么我们要先对强连通分量尽行缩点处理，将每一个强连通分量作为一个整体,之后再依据层次关系构造拓扑序，利用拓扑序找到最长的一条序列。 算法讲解 代码参考 测试数据：
4 4 1 2 2 3 3 4 4 1
5 3 1 2 2 3 3 4
9 9 5 4 4 1 1 3 3 2 2 1 1 6 6 7 7 8 8 9
5 5 1 2 2 3 3 4 4 1 5 1
代码实现：
;struct E{int from,to,next;bool sign;};int N,M;int result;int edgenum;//边的数目int top,cnt,Time;//栈顶，强联通分量数目，时间轴E edge[MAX_M];head[MAX_N];indegree[MAX_N];DFN[MAX_N];Stack[MAX_N];<tarjan(int u);//查找强连通分量void tarjan_ini(int all);void suodian();//缩点函数，按照每个强连通分量构造拓扑序int bfs();int main(){//freopen(“in.txt”,”r”,stdin);while( scanf(“%d%d”,&N,&M) != EOF ){int a,b;edgenum = 0;memset(head,-1,sizeof(head));while( M– ){scanf(“%d%d”,&a,&b);add(a,b);}tarjan_ini(N);suodian();result = bfs();printf(“%d\n”,result);}return 0;}void tarjan_ini(int all){memset(DFN,-1,sizeof(DFN));//初始化三个指针top = Time = cnt = 0;for( int i = 1; i <= all; i++ ){//查找每一个未被遍历的点的强连通分量if( DFN[i] == -1 ){tarjan(i);}}}//递归查找强连通分量void tarjan(int u){//标记时间戳DFN[u] = Low[u] = ++Time;//入栈，注意这里的前++Stack[++top] = u;instack[u] = true;//查找所有与u相邻边，寻找强连通分量for( int i = head[u]; i != -1; i = edge[i].next ){E tmp = edge[i];//未被访问节点if( DFN[tmp.to] == -1 ){tarjan(tmp.to);//u或u的子树所能追溯到的最早的栈中节点Low[u] = min(Low[u],Low[tmp.to]);}( instack[tmp.to] ){Low[u] = min(Low[u],DFN[tmp.to]);}}//u为强连通分量节点，弹栈，所有元素存储到一个vector数组if( DFN[u] == Low[u] ){int now;cnt++;bcnt[cnt].clear();do{//弹栈，注意这里的后–now = Stack[top–];//标记属于哪一个强连通分量belong[now] = cnt;instack[now] = false;bcnt[cnt].push_back(now);}while( now != u );//弹到根节点截止}}void suodian(){for( int i = 1; i <= cnt; i++ ){G[i].clear();indegree[i] = 0;}//利用所有不在某一个强连通分量内部的边构造拓扑序for( int i = 0; i < edgenum; i++ ){int u,v;u = belong[edge[i].from];v = belong[edge[i].to];if( u != v ){indegree[v]++;G[u].push_back(v);}}}void add(int u,int v){E tmp = {u,v,head[u],false};edge[edgenum] = tmp;head[u] = edgenum++;}int bfs(){int tmp;queue<int> Q;for( int i = 1; i <= cnt; i++ ){if( indegree[i] == 0 ){Q.push(i);//初始权值为强连通分量的sizedis[i] = bcnt[i].size();}else{dis[i] = 0;}}while( !Q.empty() ){int u = Q.front();Q.pop();int len = G[u].size();for( int i = 0; i < len; i++ ){int v = G[u][i];//叠加找到最大权值dis[v] = max(dis[v],(int)bcnt[v].size()+dis[u]);//若该图为一个强连通图，不会进入这里更新//tmp = max(tmp,dis[v]);indegree[v]–;if( indegree[v] == 0 ){Q.push(v);}}}//得到结果tmp = 1;for( int i = 1; i <= cnt; i++ ){tmp = max(tmp,dis[i]);}return tmp;}
启程了，人的智慧才得以发挥。
