目录
定义
割点
如果删除无向图中的某个点会使无向图的连通分量数增多,则把这个点称为割点。
割边(桥)
如果删除无向图中的某条边会使无向图的连通分量数增多,则把这个点称为割边(桥)。
关系
桥的两端可以有割点。
算法
求割点
割点:存在子树最高只能到达这个点自己
dfn[x]
:x的dfs序
low[x]
:不经过父节点,x能到达的最小序号
low[x] = min(dfn[x], low[y]);
如果x的某个儿子有:
dfn[x] <= low[y]
,那么x是割点
根节点要特判:根节点儿子数>1才是割点
伪代码
void tarjan(int x)
{
dfn[x] = low[x] = ++clk;
bool cut = false;
枚举邻居y:
if(!dfn[y])
{
tarjan(y);
low[x] = min(low[x],low[y]);
if(dfn[x] <= low[y]) cut = true;
}
else low[x] = min(low[x],dfn[y]);
if(x是根节点&&儿子数<=1) cut = false;
if(cut) ans++;
}
for(i -> n)
if(dfn[i] == 0)
tarjan(i);
模版
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int n, dfn[110], low[110], ans, clk;
vector<int> g[110];
void tarjan(int x)
{
dfn[x] = low[x] = ++clk;
bool cut = false;
int child = 0;
for(int i = 0;i < g[x].size();i++)
{
int y = g[x][i];
if(!dfn[y])
{
tarjan(y);child++;
low[x] = min(low[x],low[y]);
if(dfn[x] <= low[y]) cut = true;
}
else low[x] = min(low[x],dfn[y]);
}
if(x==1 && child<2) cut = false;
if(cut) ans++;
}
int main()
{
while(1)
{
scanf("%d",&n);if(n==0) break;
for(int i = 1;i <= n;i++) g[i].clear();
memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));ans = clk = 0;
while(1)
{
int x;
scanf("%d", &x);
if(x == 0) break;
while(1)
{
int y;char c;
scanf("%d%c", &y, &c);
g[x].push_back(y);
g[y].push_back(x);
if(c == '\n') break;
}
}
tarjan(1);
printf("%d\n", ans);
}
return 0;
}
标签:tarjan,int,图论,割点,dfn,low,include
From: https://www.cnblogs.com/ghivan911/p/17487377.html