记录编号 |
535574 |
评测结果 |
AAAAAAAAAA |
题目名称 |
备用交换机 |
最终得分 |
100 |
用户昵称 |
猎户星座 |
是否通过 |
通过 |
代码语言 |
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;
}