强连通分量tarjan

引言

强连通分量本质上是处理一个有向有环图(如果在这样的图上搞事情可能会死循环)变成一个有向无环图
强连通分量上的点可以互相到达
所以针对一些问题(我也没搞明白究竟是哪种问题)例如:

给你一张有向图，每个点都有一个点权（不是边权了哦），且每一个点都可以经过任意多次，但是点权只能加一次，求这张图的最大权值

要是将最短路的模板改一下,会出现环t飞,所以先缩点然后再跑一遍最短路(改一下)

维护

vector<int> G[maxn];//存图
s[top]//栈，存放答案
int vis[maxn];//标记点是否在栈中
int dfn[maxn];//节点i的时间戳
int low[maxn];//节点i能够回溯到的最早位于栈中的节点。（子树的根，可以理解为并查集的“祖先”一类的东西）
int color[maxn];//每个点属于第几个强联通分量
int colornum;//强连通分量的个数
int cnt;//当前时间

求强连通分量操作

先将节点标号并入栈
先访问所有节点
如果访问到的节点没有被访问过则访问一下
然后用所有被访问到并且在栈内(因为如果不在栈内说明已经被弹出,不可能构成强连通分量)的节点更新自身的 \(low[]\) 数组
最后判断本节点是否为栈顶
如果是则将本强连通分量的所有元素弹出并染色
因为栈是先进先出原则所以不用担心有重叠问题

代码P2863

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int low[N],dfn[N],s[N],col[N],vis[N];
int cnt,top,u,v,n,m,colnum,ans;
vector<int>b[N];
void dfs(int x){
	dfn[x]=low[x]=++cnt;
	s[++top]=x;
	vis[x]=1;
	for(auto i:b[x]){
		if(!dfn[i])  dfs(i);
		if(vis[i])  low[x]=min(low[i],low[x]);//如果不在栈中说明他到达不了x,不可能构成强连通分量 
	}
	if(dfn[x]==low[x]){
		colnum++;
		int j=0;
		while(s[top]!=x){
			j=1;
			col[s[top]]=colnum;
			vis[s[top]]=0;
			top--;
		}
		col[x]=colnum;
		vis[x]=0;
		top--;
		if(j)  ans++;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])  dfs(i);
	}
	printf("%d",ans);
}

缩点操作

将所形成的各个强连通分量重新赋值并建边
形成新的有向无环图
针对于P2341的解析
因为喜欢可以传递
所以一个强连通分量中的牛都是互相喜欢的
所以进行缩点操作后的牛如果有且仅有一头牛它的出度为零
则证明缩点后的图是有向联通的
则出度为零的强连通分量的元素个数则为被所有牛喜欢的牛
我们考虑为什么出度不为零的牛不被所有牛喜欢
因为如果它指向的牛还有反过来指向它则它们就在同一个强连通分量中了
不符合我们已经缩点的事实

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int vis[N],dfn[N],s[N],low[N],col[N],id[N],c[N],num[N];
int top,u,v,cnt,ans,n,m,colnum;
vector<int>b[N];
void dfs1(int x){
	dfn[x]=low[x]=++cnt;
	s[++top]=x;
	vis[x]=1;
	for(auto i:b[x]){
		if(!dfn[i])  dfs1(i);
		if(vis[i])  low[x]=min(low[i],low[x]);
	}
	if(dfn[x]==low[x]){
		colnum++;
		while(s[top]!=x){
			vis[s[top]]=0;
			col[s[top]]=colnum;
			num[colnum]++;
			top--;
		}
		col[s[top]]=colnum;
		num[colnum]++;
		vis[x]=0;
		top--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])  dfs1(i);
	}
	for(int i=1;i<=n;i++){
		for(auto j:b[i]){
			if(col[i]!=col[j]){
				c[col[i]]++;
			}
		}
	}
	for(int i=1;i<=colnum;i++){
//		printf("i=%d id=%d %d %d\n",i,id[i],col[i],c[id[i]]);
		if(!c[i]){
			if(ans){
				printf("0");
				return 0;
			}
			ans=num[i];
		}  
	}
	printf("%d",ans);
}