#67. 新年的毒瘤

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://uoj.ac/problem/67

Description

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

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

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

Input

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

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

Output

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

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

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

Sample Input

Sample Output

3
4 5 6

HINT

题意

题解：

正解需要你理解什么叫做树。如果你对树的理解仅仅是“长得像树的家伙”就完蛋了。

我们需要用一个定义来规定什么叫做树。我们可以理解成，有 n−1 条边的无向连通图。“有 n−1 条边” 提示我们最终图里有 n−2 条边，所以你需要删一个度数为 m−(n−2) 的结点。

考虑第二个条件，也就是说删掉这个点后剩下的图仍然连通，所以这个点不是割点就行了。

所以用 Tarjan 算法求割点，然后输出所有不是割点且度数满足条件的结点就行了。可以获得 100 分。（貌似这样能神奇地过掉 m=n−2 的情况……555……）

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

struct edge

{

    int v,next;

};

edge e[maxn];

int cnt,head[maxn];

void insert(int x,int y)

{

    e[cnt].v=y;

    e[cnt].next=head[x];

    head[x]=cnt;

    cnt++;

}

int n,m,times,rootCnt;

int deg[maxn],dfn[maxn],low[maxn];

bool state[maxn],cut[maxn];

void tarjan(int u,int pre)

{

    dfn[u]=low[u]=++times;

    state[u]=;

    for(int i=head[u];i!=-;i=e[i].next)

    {

        int v=e[i].v;

        if(v==pre)

            continue;

        if(!state[v])

        {

            tarjan(v,u);

            low[u]=min(low[u],low[v]);

        }

        else if(state[v]==)

            low[u]=min(low[u],dfn[v]);

    }

    if(dfn[pre]<=low[u])

    {

        if(pre==)

        {

            rootCnt++;

        }

        else

            cut[pre]=;

    }

}

int main()

{

    //freopen("test.txt","r",stdin);

    n=read(),m=read();

    int a,b;

    for(int i=;i<=n;i++)

        head[i]=-;

    for(int i=;i<m;i++)

    {

        a=read(),b=read();

        insert(a,b);

        insert(b,a);

        deg[a]++;

        deg[b]++;

    }

    tarjan(,);

    if(rootCnt>)

        cut[]=;

    int ans=;

    for(int i=;i<=n;i++)

    {

        if(!cut[i]&&(m-deg[i])==n-)

            ans++;

    }

    printf("%d\n",ans);

    for(int i=;i<=n;i++)

        if(!cut[i]&&(m-deg[i])==n-)

            printf("%d ",i);

    printf("\n");

}

毒瘤