UOJ67 新年的毒瘤 题解

题目链接：#67. 新年的毒瘤

题意：

辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。

这个长着毒瘤的树可以用 \(n\) 个结点 \(m\) 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。

现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。

输入格式：

第一行两个正整数 \(n, m\)，表示有 \(n\) 个点 \(m\) 条边。保证 \(n \geq 2\)。

接下来 \(m\) 行，每行两个整数 \(v, u\)，表示 \(v\) 和 \(u\) 之间有一条无向边。\(1 \leq v, u \leq n\)。保证没有重边和自环。

输出格式：

第一行一个正整数 \(n_s\)，表示这个图中有 \(n_s\) 个结点是毒瘤。

接下来一行，共 \(n_s\) 个整数，每个整数表示一个毒瘤结点的编号。请按编号从小到大的顺序输出。

数据保证图中至少存在一个毒瘤结点。

数据范围：

\(2 \le n ,m \le 10^5\) 。

这个题有一种 CodeForces 的味道

注意到删掉一个毒瘤结点后，还剩下 \(n-1\) 个结点和 \(n-2\) 条边。

那么这个毒瘤结点一定满足

• 度数为 \(m-n+2\) 。（要保证 \(n-2\) 条边）
• 不是割点。（因为割点删掉后图就不连通了）

特别地，如果原图不是连通图，又因为至少有一个毒瘤结点

不难发现这个时候这张图就是一个单点加一堆点，显然只有这一个点可以选。

时间复杂度 \(\mathcal{O}(n+m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,m,cnt,pos=1,head[N],p[N],in[N],cut[N],dfn[N],low[N];
struct Edge { int u,v,next; } e[N*2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u,int f)
{
    static int tim = 0; int C = 0;
    dfn[u] = low[u] = ++tim;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            ++C; Tarjan(v,u); down(low[u], low[v]);
            if(f && dfn[u] <= low[v]) cut[u] = 1;
        }else if(v != f) down(low[u], dfn[v]);
    }
    if(!f && C>1) cut[u] = 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v; ++in[u]; ++in[v];
        addEdge(u,v); addEdge(v,u);
    } Tarjan(1,0);
    for(int i=1; i<=n; i++)
        if(!cut[i] && in[i] == m - n + 2) p[++cnt] = i;
    cout << cnt << '\n';
    for(int i=1; i<=cnt; i++) cout << p[i] << " \n"[i==cnt];
    return 0;
}