记录编号 535574 评测结果 AAAAAAAAAA
题目名称 备用交换机 最终得分 100
用户昵称 Gravatar猎户星座 是否通过 通过
代码语言 C++ 运行时间 0.005 s
提交时间 2019-07-05 15:17:38 内存使用 13.71 MiB
显示代码纯文本
/*#include<bits/stdc++.h>
#define N (1000000+10)
using namespace std;
int a[N],nxt[N],head[N],dfn[N],low[N],cnt,k;
bool cut[N],bst[N];
void add(int x,int y){
    a[++k]=y; 
	nxt[k]=head[x];
	head[x]=k;
}
void tarjan(int u,int mr){
    int rc=0;
    dfn[u]=low[u]=++cnt;
    for(int p=head[u];p;p=nxt[p]){
        int v=a[p];
        if(!dfn[v]){
            tarjan(v,mr);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=mr) cut[u]=true;
            if(u==mr) rc++;
        }
        low[u]=min(low[u],dfn[v]);
    }    
    if(u==mr&&rc>=2)cut[mr]=true;
}
int main(){
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,i);
    }
    for(int i=1;i<=n;i++)if(cut[i])ans++;
    printf("%d\n",ans);
    for (int i=1;i<=n;i++)if(cut[i])printf("%d ",i);
    return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int a[maxn][maxn]={{0}},color[maxn]={0},col=0,first[maxn],low[maxn],tim=0,ch[maxn]={0},prt[maxn]={0},n,x,y;
bool ge[maxn]={false};
void dfs(int x){
    color[x]=-col;
    low[x]=first[x]=++tim;
	for(int y=1;y<=n;y++)if(a[x][y]>0){
    	a[x][y]=-a[x][y];
    	if(!color[y]){
    		ch[x]++;
    		prt[y]=x;
    		dfs(y);
    		low[x]=min(low[x],low[y]);
    	}
    	else if(color[y]<0){
    		low[x]=min(low[x],first[y]);
    	}
    	a[x][y]=-a[x][y];
    }
    color[x]=col;
}
int main(){
    freopen("gd.in","r",stdin);
    freopen("gd.out","w",stdout);
    scanf("%d",&n);
    while(scanf("%d%d",&x,&y)==2)a[x][y]=a[y][x]=1;
    for(int i=1;i<=n;i++)if(!color[i]){
    	col++;
    	dfs(i);
    }
    int m=0;
    for(int i=1;i<=n;i++){
    	if(!prt[i]&&ch[i]>1)ge[i]=true;
    	if(prt[prt[i]]&&low[i]>=first[prt[i]])ge[prt[i]]=true;
    }
    for(int i=1;i<=n;i++)if(ge[i])m++;printf("%d\n",m);
    for(int i=1;i<=n;i++)if(ge[i])printf("%d\n",i);
    return 0;
}