点击量：222

   tarjan求割点的变形。

目录

题目背景

$ \mathrm{Fanvree}$很聪明，解决难题时他总会把问题简单化。

 

例如，他就整天喜欢把图转化为树。但是他不会缩环，那他怎么转化呢？

 

题目描述

这是一个有$ n$个点$ m$条双向边的图，$ \mathrm{Fanvree}$会选定一个节点， 然后删掉这个节点和这个点连出去的边， 如果变成了一棵树， 那么这个节点便是可行的， 什么是树呢？ 树也即无简单环的无向连通图。

 

告诉$ \mathrm{Fanvree}$可能的节点是什么。

 

输入输出格式

输入格式：

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

 

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

 

输出格式：

第一行一个正整数$ ns$，表示这个图中有$ ns$个结点可选。

 

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

数据保证图中至少存在一个可选的结点。

 

输入输出样例

输入样例#1：

6 6

1 2

1 3

2 4

2 5

4 6

5 6

输出样例#1：

3

4 5 6

说明

对于$ 40$%的数据，$ n,m\le 1,000,$

 

另存在$ 10$%的数据，$ m=n-1,$

 

另存在$ 20$%的数据，$ m=n,$

 

对于$ 100$%的数据，$ n,m\le 100,000.$

 

命题人:$ \mathrm{Jasonvictoryan}$

题解：

   对于40%的数据来说，$ O(n^2)$是可以过的。枚举每个点作为题意要求点时，原图是否为一棵树。

   那么另外30%的数据分别为”n=m”/”n=m+1″，一眼看上去，好像分别是一个环和一棵树。不过这两种情况并不全面，为什么呢？如果n=m+1，当有点孤立出来时，图不再连通，点所不在的连通块就可能不是一棵树；而同时，当n=m时，可能是环的变种，像下图这样，一棵树中两个没有直接相连的点被连上一条边，也会成环，这只是最特殊的情况。因此30分也不好得。

   重新回到题面上来，题目让我们把给出的图删掉一个点后变成一棵树。对于这个图，我们所了解的是它的n个点，m条边。而目标树则是确定的，因为删掉一个点后，它一定会剩下n-1个点，n-2条边。因此我们对于原图上的每个点，删掉它会移除图中的与它的度个数相同条边。而我们要把m变为n-2，并且只删除一个点，那么我们就要删掉一个度为m-(n-2)的点。

   树是一棵无向连通图，为了保证图的连通性，删去的这个点不能是图的割点，因此tarjan预处理一下，就知道哪个点是割点，哪个点不是。最后再枚举点，判断度数是否合法就可以了（度数在读边时处理出来）。

Code：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::min;
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[201000];
int head[101000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int d[101000];
int dfn[101000],low[101000],cnt=0;
int cut[101000];//是否为割点
void tarjan(int x,int from)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            if(dfn[e[i].n])
                low[x]=min(low[x],dfn[e[i].n]);
            else
            {
                tarjan(e[i].n,x);
                low[x]=min(low[x],low[e[i].n]);
            }
            if(low[e[i].n]>dfn[x])
                cut[x]=1;
        }
}
int ans[101000];
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        d[u]++;//度+1
        d[v]++;
    }
    tarjan(1,1);
    cnt=0;
    for(int i=1;i<=n;i++)
        if(!cut[i]&&d[i]==m-(n-2))
            ans[++cnt]=i;
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d ",ans[i]);
    return 0;
}