tarkjan求无向图割点模板

时间:2024-10-26 22:04:02
 #include<bits/stdc++.h>
using namespace std;
typedef long long ll; int n,m;
const int maxn=1e5+;
const int maxm=maxn<<;
struct node
{
int to;
int nxt;
}e[maxm];
int head[maxn];
int tot;
int id;
int root;
int low[maxn];
int num[maxn];
bool vis[maxn];
int pa[maxn];
int cnt=;
int art[maxn];
void init()
{
memset(head,-,sizeof(head));
tot=;
id=;
memset(low,-,sizeof(low));
memset(num,-,sizeof(num));
memset(vis,false,sizeof(vis));
memset(pa,-,sizeof(pa));
cnt=;
memset(art,,sizeof(art));
}
void add(int u,int v)
{
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
void findArt(int u)
{
vis[u]=true;
low[u]=num[u]=++id;
for(int i=head[u];i!=-;i=e[i].nxt)
{
int v=e[i].to;
//树边
if(!vis[v])
{
pa[v]=u;
findArt(v);
if(low[v]>=num[u]&&u!=root)
{
art[cnt++]=u;
}
low[u]=min(low[u],low[v]);
}
else if(pa[v]!=u) //回退边
{
low[u]=min(low[u],num[v]);
}
}
} void printArt()
{
int tmp=;
for(int i=head[root];i!=-;i=e[i].nxt)
{
if(pa[e[i].to]==root) tmp++;
}
if(tmp>=) art[cnt++]=root;
for(int i=;i<cnt;i++)
{
printf("%d ",art[i]);
}
puts("");
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u,v;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
root=;
findArt(root);
printArt();
}
return ;
}

Tarkjan求无向图割点

http://www.cnblogs.com/llhthinker/p/4954082.html