一.模板介绍

模板题

1.定义

给定一张有向图，若存在一个点集，该点集内的点可通过路径任意到达其他所有点，则称该点集为一个强联通分量。(一个点也可为一个强联通分量)

2.算法tarjan

结果：将强联通分量缩成一个点，让一个有环图变成一张无环图

#include<bits/stdc++.h>
using namespace std;
const int N=20005;
const int M=1e5+5;
struct ppp {
	int u,v,next;
} e[2*M];
int vex[N],k;
int dfn[N],low[N],cnt;
int stk[N],top,color[N],co,ans[N],instk[N];
int n,m;
//dfn为次序，low为该点所能遍历的次序最早的点 
void add(int u,int v) {
	k++;
	e[k].u=u;
	e[k].v=v;
	e[k].next=vex[u];
	vex[u]=k;
	return;
}
void tarjan(int u) {
	dfn[u]=low[u]=++cnt;
	instk[u]=1;
	stk[++top]=u;//用栈储存强连通，u点入栈 
	for(int i=vex[u]; i; i=e[i].next) {
		int v=e[i].v;
		if(!dfn[v]) {
			tarjan(v,root);
			low[u]=min(low[v],low[u]);
			//如果v能遍历到的点比u能遍历到的最小点小，就改值 
		}
		else if(instk[v])low[u]=min(low[u],dfn[v]);
		//如果v的次序比u的遍历到的最小点小，就改值 
	}
	if(dfn[u]==low[u]){//则该点为强连通的最早点 
		co++;
		while(1){
			int t=stk[top];//从栈顶到这个点的所有点，都是该强联通分量的点集 
			color[t]=co;//属于一个强联通分量的点颜色相同 
			top--;
			instk[t]=0;//出栈 
			if(t==u)break;
		}
	} 
}
void solve(){
	co=n; //如果需要对缩完后的点建图，则co要从n+1开始
	for(int i=1; i<=n; i++) {
       if(!dfn[i])tarjan(i,i);
	}
	for(int u=1;u<=n;u++){
		for(int i=vex[u];i;i=e[i].next){
			int v=e[i].v;
			if(color[u]!=color[v])add(color[u],color[v]);
			//后来是以缩点后的强联通分量颜色来建无向图
		}
	}
}
int main() {
	int u,v;
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	solve(); 
	return 0;
}  

3.开始刷题

例题1：消息扩散

只需要在tarjan完之后，求入度为0的点的数量即可

void xxks(){
	int ans=0;
	for(int u=1;u<=n;u++){
		for(int i=vex[u];i;i=e[i].next){
			int v=e[i].v;
			if(color[u]!=color[v])in[color[v]]++;
			//求入度为0的点为扩散源 
		}
	}
	for(int i=1;i<=co;i++){
		if(in[i]==0)ans++;
	}
	cout<<ans;
} 

二.割点

割点模板题

1.定义

给定一张无向连通图，若存在点u满足删除该点后，连通图不再连通，则该点u为该图的割点

2.算法tarjan

过程

tarjan跑一个深搜优先树
对于根节点：若其有两个以上的孩子，则该点为割点
对于非根点：若从u出发跑，不能到达u的上层，则u点为割点

根据定义很好写出代码

void tarjan(int u,int root) {
	dfn[u]=low[u]=++cnt;
	instk[u]=1;
	stk[++top]=u;
	int child=0;
	for(int i=vex[u]; i; i=e[i].next) {
		int v=e[i].v;
		if(!dfn[v]) {
			tarjan(v,root);
			low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]&&u!=root)cut[u]=1;
            //由子节点出发能到的最早点在该节点后面或等于该节点则为割点
			//不为if(low[u]>=dfn[u])的原因:只要由一个子节点满足情况则u就为割点 
			if(u==root)child++;//统计根节点的孩子数 
		}
		low[u]=min(low[u],dfn[v]);
	}
	if(u==root&&child>=2)cut[u]=1;//根节点有两个子树则为割点 
	if(dfn[u]==low[u]){
		co++;
		while(1){
			int t=stk[top];
			color[t]=co;
			top--;
			instk[t]=0;
			if(t==u)break;
		}
	} 
}