UOJ#67 新年的毒瘤

2018-11-07 16:28:38


题意:一个无向图,如果删除一个点之后剩下的图是一棵树,那么这个点是毒瘤点,问哪些点是毒瘤点


  • 删除一个点之后,剩下 $n-1$ 个点构成的树有 $n-2$ 条边,所以毒瘤点的度数一定是 $m-n+2$

  • 树是连通图,所以毒瘤点一定不是图的割点

    $tarjan$ 求出割点之后判断即可

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,num,ans,head[N],d[N],fa[N],dfn[N],low[N],tim,cut[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num; ++d[to];
}
void tarjan(int k)
{
    dfn[k]=low[k]=++tim; int cnt=0;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!dfn[v])
        {
            fa[v]=fa[k]; tarjan(v);
            low[k]=min(low[k],low[v]);
            if (low[v]>=dfn[k]&&k!=fa[k]) cut[k]=1;
            if (k==fa[k]) ++cnt;
        }
        low[k]=min(low[k],dfn[v]);
    }
    if (k==fa[k]&&cnt>1) cut[k]=1;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    for (reg int i=1;i<=n;i++) fa[i]=i;
    for (reg int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
    for (reg int i=1;i<=n;i++)
      if (d[i]==m-n+2&&!cut[i]) ++ans;
    printf("%d\n",ans);
    for (reg int i=1;i<=n;i++)
      if (d[i]==m-n+2&&!cut[i]) printf("%d ",i);
    return 0;
}