[笔记]tarjan+缩点

算法用途:

tarjan可以求强连通分量，缩点则是将一个强连通分量缩成一个点

tarjan

概念

1.有向图的强连通分量：再有向图(G)中，如果两个顶点(V_i,V_j)间有一条从(V_i)到(V_j)的有向路径同时还有一条从(V_j)到(V_i)的有向路径，则称这两个点强连通，在一个图的子图中，任意两点可以相互到达则称这组成了一个强连通分量。

2.一个单独的点也是一个强连通分量。

算法描述

变量：

1.(dfn)数组:(dfn[i])表示(i)这个点再(dfs)时是第几个被搜到的

2.(low[i]):表示的是(i)这个节点和它的子孙节点中(dfn)最小的值

3.(stack):表示所有可能构成强连通分量的点，其实就是一个栈

算法过程

一画图理解

tarjan的第一步是对整个图进行(dfs),搜完后会得到一棵(dfs)树，举个例子.这个树时有向的，显然在这个树上是不会存在环的，因此能产生环的只有可能是一条指向已经访问(搜索)过的边，也就是图中的红边和蓝边。经过观察发现，红边可以产生一个强连通分量，而蓝边不行，因为红边是由(6)号节点指向它的祖先(4)号节点的，这种红边称为后向边,而蓝边则指向两个没有父子关系的点，这种边称为横叉边，横叉边不一定产生环，而后向边一定产生环。

知道了以上结论后就开始深搜首先会搜到这样的图,此时(stack = {1,2,3})，而(3)没有多余的指向其它点的边，因此将(3)弹出栈，单独作为一个强连通分量，继续深搜，会搜到这样一个图,此时(stack = {1,2,7}) 发现节点(7)指向已经搜索过的节点(3),是上述两种可能存在环的情况，而此时(3)不再(stack)中，因此不存在环，将(7,2)依次弹出栈中，单独作为一个强连通分量，再次深搜，会搜到这样一个图,此时(stack = {1,4,5,6}) 发现节点(6)有一条连向其他节点的边，即红边，指向的是节点(4),而这个点已经搜索过了，符合上面说的产生环的条件，而此时发现节点(4)已经在(stack)中说明这是一条后向边，可以产生环，因此(4)~(6)号节点中的所有点组成一个强连通分量。算法结束

但实际情况可能更复杂,这里出现了大环套小环的问题，我们需要对(dfs)过程稍作修改(见下)。

二算法完整步骤

1.首先初始化(dfn[u] = low[u] = 第几个被搜索到)，但并不是一开始就先跑一遍深搜，而是边做边赋值，具体见代码

2.将当前搜索的节点(u)存入(stack)中

3.遍历每一个与节点(u)相连的点，如果遍历到的点的(dfn)值为(0)则说明这个点之前没有被访问过，那么就对这个没有被访问过的点(假设为(v))进行深搜并且更新(low)数组的值:low[u] = min(low[u],low[v]),如果与(u)相连的点(假设为(g))已经被搜索过了,也就是说dfn[g]!=0，此时就更新(low[u])的值：low[u] = min(low[u],dfn[g]),这样就可以保证(low[u])存储的是最先被(dfs)到的点，也就保证了找的环是最大的。但为什么是用(dfn[g])来更新呢？因为节点(g)可能是另一个强连通分量里的节点，只是还没有出栈，因此节点(u)可能不能到达(low[g])，但(u)一定可以到达(dfn[g])。

4.那么什么时候说明找到了一个完整的最大的环呢？当我们找到一个点(u)满足low[u] == dfn[u]时，说明这个点的子树中不存在比这个点先搜到的点，则节点(u)为它所在的强连通分量里的根节点，所以将(stack)中(u)及它之后的点全部弹出，这就是一个强连通分量。

缩点

算法描述

缩点其实很好理解，也很好实现，只需要新建一个(col)数组，用来将同一个连通块内的点染成一个颜色。具体实现看代码。缩完点后的图是一个有向无环图，各个缩完的点由跨越不同强连通分量的边来连接。

例题应用

原题链

题目分析

首先建图，如果(A)认为(B)受欢迎，则连一条从(B)到(A)的有向边，这样更方便求强连通分量。然后用(tarjan)求出所有的强连通分量，再缩点，找到一个出度为(0)的缩完后的点，这就是答案，因为缩完点后的图是一个有向无环图，如果一个缩点有出度，则它一定不能被它连出去的那个缩点的牛所喜欢；而一个缩完点后的图中，也不能出现两个没有出度的缩点，因为这样它们就不能被对方缩点里的牛所喜欢，因此我们的答案是只有一个缩点出度为(0)的图中那个缩点的大小

代码（tarjan+缩点 & AC code）

#include <bits/stdc++.h>
using namespace std;
struct node{
	int to,next;	
}edge[100010];
int fir[100010],dfn[100010],low[100010],col[100010],num,tot,coln,size[100010],degree[100010];
stack < int > s;
void add(int x,int y){
	tot++;
	edge[tot].to = y;
	edge[tot].next = fir[x];
	fir[x] = tot;
}
void tarjan(int k){
	low[k] = dfn[k] = ++num;
	s.push(k);
	for(int i = fir[k];i;i = edge[i].next){
		int x = edge[i].to;
		if(!dfn[x]){
			tarjan(x);
			low[k] = min(low[k],low[x]);
		}
		else if(!col[x]){//发现后向边 
			low[k] = min(low[k],dfn[x]);
		}
	}
	if(low[k] == dfn[k]){//找到了一个强连通分量的根节点 
		col[k] = ++coln;//缩到一个点里 
		++size[coln];//更新缩点的大小 
		while(s.top() != k){
			col[s.top()] = coln;//缩点 
			++size[coln];//更新缩点的大小 
			s.pop();
		}
		s.pop();//千万不要忘记这一步，要将k节点弹出 
	}
	return;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(y,x);
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i])
			tarjan(i); 
	} 
	for(int i = 1;i <= n;i++){
		for(int j = fir[i];j;j = edge[j].next){
			int x = edge[j].to;
			if(col[x] != col[i]){//颜色不同说明不在一个块中，所以出度增加 
				++degree[col[x]];//因为建的是反向边，所以其实是从x连到i 
			}	
		}
	} 
	int flag = 0;//记录有多少出度为0的缩点，如果大于1个则答案为0
	int ans = 0; 
	for(int i = 1;i <= coln;i++){
		if(degree[i] == 0){
			++flag;
			ans = size[i];
		}
	} 
	if(flag != 1){
		printf("0
");
	}
	else printf("%d
",ans);
	return 0;
}