学步园

强连通分量：

简言之 就是找环（每条边只走一次，两两可达）

孤立的一个点也是一个连通分量

使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点）

定义：

int Time, DFN[N], Low[N];

DFN[i]表示 遍历到 i 点时是第几次dfs

Low[u] 表示 以u点为父节点的 子树 能连接到 [栈中] 最上端的点

int Stack[N], top; //栈用来记录所有走过的点（因为是dfs过程，首先从根节点走到叶子节点再进行处理 所以栈中存的是
唯一一条路径 （无分叉））

tarjan的过程就是dfs过程

是对树dfs （对于一些会连会 走过的边 （成为反向边|横向边））

显然图中只有树边和这样的反向边

对于树，加一条边就会成环，显然 对于反向边的2个端点 [u,v]  （这样得到一个环是 [u, u到v的路径, v]  ，之前提到因为dfs所以栈中存的是唯一路径，退栈就能得到u->v的路径）

从dfs算法可以得到每个点至多入栈一次，因此每个点都只存在于一个强连通分量中

图中 红线和蓝线（蓝线为左边中间那条）为反向边

注意Low【】数组的定义：low[u]  表示u的子树中 所有反向边能连接到 最高的 u的父节点 （所以用时间戳数组DFN[]来判断反向边连接到的节点是u的子节点还是u的父节点（即数值小的就是父节点）

当现在dfs 到 u点，子节点 v 的反向边，能走到最高处是 f 点，所以 Low[ v ] = DFN[ f ];

根据定义 Low[u] = Low[ v ] = DFN[ f ];

if( DFN[ u ] >= Low[ u ] ) 则u 是割点

图中 DFN[ v ] > Low[ v ] , DFN[ u ] > Low[ u ] ，而这个环（v u f ) 以v为起点 ，则 f 为终点 因为点f ： DFN[ f ] == Low[ f ]

所以当 回溯到 f点时， if( DFN[f] == Low[ f ] ) 则路径上的所有点都是割点（即栈中所有点）

这样就能得到 环【v u f】

#define N 22000
//N为点数
#define M 55000
//M为边数

struct Edge{
	int from, to, nex;
	bool sign;//表示边是否使用过（处理重边的情况）
}edge[M];
int head[N], edgenum;
void addedge(int u, int v){
	Edge E={u, v, head[u], false};
	edge[ edgenum ] = E;
	head[u] = edgenum++;
}

int DFN[N], Low[N], Stack[N], top, Time;
int taj;//连通分支标号
int Belong[N];//Belong[i] 表示i点属于的连通分支
bool Instack[N];

void tarjan(int u ,int fa){  
	DFN[u] = Low[u] = ++ Time ;  
	Stack[top ++ ] = u ;  
	Instack[u] = 1 ;  

	for (int i = head[u] ; i!=-1 ; i = edge[i].nex ){  
		int v = edge[i].to ;  
		if(DFN[v] == -1)
		{  
			tarjan(v , u) ;  
			Low[u] = Min(Low[u] ,Low[v]) ;
			if(DFN[u] < Low[v])
			{
				edge[i].sign = 1;//为割桥
			}
		}  
		else if(Instack[v]){  
			Low[u] = Min(Low[u] ,DFN[v]) ;  
		}
	}  
	if(Low[u] == DFN[u]){  
		int now ;
		taj ++ ; 
		do{
			now = Stack[-- top] ;  
			Instack[now] = 0 ; 
			Belong [now] = taj ;
		}while(now != u) ;
	}
}

void tarjan_init(){
	memset(head, -1, sizeof(head)); edgenum = 0;
	memset(DFN, -1, sizeof(DFN));
	memset(Instack, 0, sizeof(Instack));
	top = Time = taj = 0;
}