在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。

【性质】

   如果u是某个强连通分量的根，那么：

（1）u不存在路径可以返回到它的祖先。

（2）u的子树也不存在路径可以返回到u的祖先。

【算法描述】

  （1）我们先对每一个顶点判断，如果已经被运行过了，则不动，否则进行拓展

  （2）对于每一个点，我们设2个值来表示（dfn和low){low[i]表示结点i的根结点的dfn值}，dfn则是结点i的时间戳

  （3）在第一次顺序遍历时，dfn[u]=low[u]=++cnt，初始化序列

  （4）然后将遍历到的点压入栈，并且置为已做过

  （5）在整个图中枚举一条以u为右端点的边(from,to)，然后判断左端点是否已经入栈，如果已经入栈，则修改low[u]:low[u]=max(low[u],dfn(to))，如果没入栈，则对其进行递归处理，返回时low[u]=min(low[u],low[to])

  （6）当出现dfn[u]==low[u]时，则表明已经出现一个强联通分量，依次弹出并消除标记即可，此时cnt++，则该作用为统计联通块数量

【总结】

  上述算法时间复杂度O(N+M)

【例题】

  codevs2822《爱在心中》

 

  很明显，对于题目的第一问，我们只需要将给出的关系图跑一遍裸的tarjan即可

  然而第二问显然就不是那么简单了，题目要求我们找出容量为n-1的联通块，这里要注意：

  不能直接计算，因为你的图已经被第一问毁了。所以要再次构图

  然后统计每个点的“爸爸”以及每个点的强联通分量个数

  再寻找为n的即可，然后依次输出

  时间复杂度O(4N+M)

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MaxN=1001;


int s[MaxN],top;
int n,m;
int ans;//联通块个数 
int dfn[MaxN],low[MaxN];
bool vis[MaxN],inq[MaxN];
int belong[MaxN];
int head[MaxN],hav[MaxN],h[MaxN];

struct graph{
	int to,next;
}G[MaxN],R[MaxN];

int cnt1=0,cnt2=0;

inline int minx(int a,int b){return a<b?a:b;}

void addedge(int u,int v){
	G[++cnt1].to=v;
	G[cnt1].next=head[u];
	head[u]=cnt1;
}

void tarjan(int u){
	dfn[u]=low[u]=++cnt2;
	s[++top]=u;
	vis[u]=inq[u]=true;
	for(int i=head[u];i!=0;i=G[i].next){
	  	if(!dfn[G[i].to]){
	  	  tarjan(G[i].to);
	  	  low[u]=minx(low[u],low[G[i].to]);
	    }
	    else 
	    	if(inq[G[i].to])
			  low[u]=minx(low[u],dfn[G[i].to]);
	  }
	if(dfn[u]==low[u]){
		ans++;
		int j=0;
		while(j!=u){
			j=s[top--];
			inq[j]=false;
			belong[j]=ans;
			++hav[ans];
		}
	}
}

void rebuild(){
	int i,j,cnt=0;
	for(i=1;i<=n;i++)
		for(j=head[i];j!=0;j=G[j].next)
	      if(belong[G[j].to]!=belong[i])
	    	{
			  R[++cnt].to=belong[G[j].to];
			  R[cnt].next=h[belong[i]];
			  h[belong[i]]=cnt;
		    }
}
void work(){
  int i,ans1=0;
  for(i=1;i<=n;i++){
  	if(!vis[i])
  	  tarjan(i);
  }
  rebuild();
  for(i=1;i<=ans;i++)
    if(hav[i]>1)ans1++;
  printf("%d\n",ans1);
  ans1=-1;
  for(i=1;i<=ans;i++)
    if(!h[i]){
    	if(ans1!=-1 || hav[i]==1)
    	  {ans1=-1;break;}
    	else
    	  ans1=i;
    }
    if(ans1==-1)printf("%d",ans1);
    else {
    	for(i=1;i<=n;i++)
    	  if(belong[i]==ans1)printf("%d ",i);
    }
}

int main(){
  scanf("%d %d",&n,&m);
  int i,u,v;
  memset(vis,false,sizeof(vis)); 
  for(i=1;i<=m;i++){
  	scanf("%d %d",&u,&v);
  	addedge(u,v);
  }
  work();
  return 0;
}

-----------------------------------------thanks for watching------------------------------------------