# Tarjan 缩点、割点和桥的模板

# 一、缩点

缩点的前提是了解强联通分量，强联通分量的定义是强联通分量中的每一个点都可以到达另一个强联通分量中的节点，缩点就是把一个强联通分量缩成一个节点来帮助我们更好完成题目任务的一种方法

例题：受欢迎的牛 G

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=20001;
stack <int  >s;
vector <int > g[N];
int low[N],dfn[N],col[N],n,m,cnt,T,count0[N],tot,in[N],out[N];
bool flag[N];
void tarjan(int pos)
{
	dfn[pos]=low[pos]=++cnt;
	s.push(pos);
	int size=g[pos].size();
	flag[pos]=true;
	for(int i=0;i<size;i++)
	{
		int to=g[pos][i];
		if(!dfn[to])
		{
			tarjan(to);
			low[pos]=min(low[pos],low[to]);
		}
		else if(flag[to])
			low[pos]=min(low[pos],low[to]);
	}
	if(dfn[pos]==low[pos])
	{
		flag[pos]=false;
		col[pos]=++tot;
		while(!s.empty() && s.top()!=pos)
		{
			flag[s.top()]=false;
			col[s.top()]=tot;
			s.pop();
		}
		s.pop();
	}
	return;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		g[i].push_back(i);
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
			tarjan(i);
	}
	for(int i=1;i<=n;i++)
    	count0[col[i]]++;
    for(int i=1;i<=n;i++)
    {
    	int size=g[i].size();
    	for(int j=0;j<size;j++)
    	{
    		if(col[i]!=col[g[i][j]])
    			in[col[g[i][j]]]=1,out[col[i]]=1;
		}
	}
	int anspos=0,ans=0;
	for(int i=1;i<=tot;i++)
	{
		if(!out[i])
		{
			ans++;
			anspos=i;
		}
	}
	if(ans>1)
		printf("0\n");
	else
		printf("%d\n",count0[anspos]);
	return 0;
}

# 二、割点

割点的定义是如果一张连通图删去此节点，那么这张连通图变为不连通图，此节点就被称为割点

例题：割点

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=200001;
int n,m,dfn[N],low[N],root,cnt;
bool flag[N],cut[N];
vector <int > g[N];
void tarjan(int cur)
{
	dfn[cur]=low[cur]=++cnt;
	int size=g[cur].size();
	int flag=0;
	for(int i=0;i<size;i++)
	{
		int to=g[cur][i];
		if(!dfn[to])
		{
			tarjan(to);
			low[cur]=min(low[cur],low[to]);
			if(low[to]>=dfn[cur])
			{
				flag++;
				if(cur!=root || flag>1)
					cut[cur]=true;
			}
		}
		else
			low[cur]=min(low[cur],dfn[to]);
	}
	return;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			root=i,tarjan(i);
	long long ans=0;
	for(int i=1;i<=n;i++)
		if(cut[i])
			ans++;
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++)
		if(cut[i])
			printf("%d ",i);
	return 0;
}

# 三、桥

桥的定义和割点很像，区别在于割点是一个点，而桥是一条边，也就是一张连通图少了一个桥就会变成非连通图

没有好的例题，直接上代码：

Code:

struct node
{
    int to,id;
    node(int tt,int ii)
    {
        to=tt,id=ii;
    }
    node()
    {
    }
};
vector <node > g[N];
int dfn[N],low[N];
bool qiao[N];

void tarjan(int cur)
{
    dfn[cur]=low[cur]=++cnt;
    int size=g[cur].size();
    for(int i=0;i<size;i++)
    {
        int to=g[cur][i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[cur]=min(low[cur],low[to]);
            if(low[to]>dfn[cur])
                qiao[g[cur][i].id]=true;
        }
        else
            low[cur]=min(low[cur],dfn[to]);
    }
    return;
}

本篇文章只贴模板，具体分析移步另一篇文章