【题目描述】：
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
现在给出一个有向图。结点个数N(<=1000)(编号1~N)，边数M(<=5000)。请你按照从小到大的顺序输出最大的强连通分量结点编号。
【输入描述】：
第一行N和M 以下M行，每行两个空格隔开的整数表示一条有向边；
【输出描述】：
输出一行，最大的强连通分量的结点（由小到大输出）
【样例输入】：
10 202 25 38 53 48 710 1010 67 72 83 28 13 81 78 107 56 49 28 67 51 8
【样例输出】：
1 2 3 5 7 8
【时间限制、数据范围及描述】：
时间：1s 空间：256M
N<=1000, M<=5000
题解：也算是较为模板的一道题吧
#include#include #include #include #include #include #include using namespace std;struct Node{ int v,w,next;}edge[5005]; int k,t,cnt;int dfn[5005],low[5005],f[5005],vis[5005],head[5005],belong[5005];stack q; void add(int u,int v){ k++; edge[k].v=v; edge[k].next=head[u]; head[u]=k;} void Tarjan(int u){ t++; dfn[u]=low[u]=t; vis[u]=1; q.push(u); for(int i=head[u];i;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(low[u]>=dfn[u]){ cnt++; int h; do{ h=q.top(); vis[h]=0; belong[h]=cnt; q.pop(); }while(h!=u); }}int main(){ int n,m,a,b; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); add(a,b); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); for(int i=1;i<=n;i++){ f[belong[i]]++; if(f[belong[i]]>f[f[0]]) f[0]=belong[i]; } for(int i=1;i<=n;i++){ if(belong[i]==f[0]) printf("%d ",i); } printf("\n"); return 0;}