洛谷 P3388 割点(割顶) 题解

时间:2023-03-09 20:14:21
洛谷 P3388 割点(割顶) 题解

题面

    割点性质:
    节点 u 如果是割点,当且仅当存在 u 的一个子树,子树中没有连向 u 的祖先的边(返祖边)。
  换句话说,如果对于一个点u,它的子节点是v,如果low[v]>=dfn[u],就代表u的子图中没有返祖边,即该节点u是割点;
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct littlestar{
int to;
int nxt;
}star[];
int head[],cnt;
void add(int u,int v)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
head[u]=cnt;
}
int dfn[],low[];
int num;
int co[];
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(fa&&low[v]>=dfn[u]){
co[u]=; //注意,不可以在这里统计割点次数,因为有的点可能会多次进入该判断语句,比如说菊花图。
}
}
else if(v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
} }
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++){
if(!dfn[i]) tarjan(i,);
}
int col=;
for(int i=;i<=n;i++){
if(co[i]){
++col;
}
}
cout<<col<<endl;
for(int i=;i<=n;i++){
if(co[i]){
cout<<i<<" ";
}
}
}