92 求助!
查看原帖
92 求助!
184500
hanzhongtlx楼主2020/10/25 21:20

RT

#include"algorithm"
#include"iostream"
#include"cstdio"
#include"cmath"
using namespace std;

#define MAXN  20005
#define read(x) scanf("%d",&x)

int n,m;
int low[MAXN],num[MAXN],vis[MAXN];
int head[MAXN],cnt=0;
int c=0;
struct node
{
    int to,nxt;
}e[MAXN*10];
int u,v;
int id=0,child=0;
int ma[MAXN];

void add(int u,int v){e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;}

void dfs(int cur,int fa)
{
    num[cur]=low[cur]=++id;
    vis[cur]=1,child=0;
    for(int i=head[cur];i;i=e[i].nxt)
    {
        int j=e[i].to;
        if(!vis[j]) 
		{
			child++;
			dfs(j,cur);
        	low[cur]=min(low[cur],low[j]);
    		if(fa&&low[j]>=num[cur]&&!ma[cur]) c++,ma[cur]=1;
			if(!fa&&child==2&&!ma[cur]) c++,ma[cur]=1;
		}
		else if(j!=fa) low[cur]=min(low[cur],num[j]); 
	}
    return;
}

int main()
{
    read(n),read(m);
    for(int i=1;i<=m;i++) read(u),read(v),add(u,v),add(v,u);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
    printf("%d\n",c);
    for(int i=1;i<=n;i++) if(ma[i]) printf("%d ",i);
    return puts(""),0;
}
2020/10/25 21:20
加载中...