「uoj #67」新年的毒瘤
辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。
这个长着毒瘤的树可以用 n 个结点 m 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。
现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。
输入格式
第一行两个正整数 n,m，表示有 n 个点 m 条边。保证 n≥2。
接下来 m 行，每行两个整数 v,u，表示 v 和 u 之间有一条无向边。1≤v,u≤n。保证没有重边和自环。
输出格式
第一行一个正整数 ns，表示这个图中有 ns 个结点是毒瘤。
接下来一行，共 ns 个整数，每个整数表示一个毒瘤结点的编号。请按编号从小到大的顺序输出。
数据保证图中至少存在一个毒瘤结点。
QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ind,cnt,top,tot; int last[100005],fa[100005],size[100005],d[100005]; int dfn[100005],low[100005],q[100005]; bool mark[100005]; struct edge{ int to,next; }e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void tarjan(int x,int fa) { dfn[x]=low[x]=++ind; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { if(!dfn[e[i].to]) { tarjan(e[i].to,x),low[x]=min(low[x],low[e[i].to]); if(low[e[i].to]>=dfn[x]&&x!=1)mark[x]=1; if(x==1)tot++; } else low[x]=min(low[x],dfn[e[i].to]); } } int main() { n=read();m=read(); for(int i=1;i<=n;i++)fa[i]=i,size[i]=1; for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); d[u]++;d[v]++; int p=find(u),q=find(v); fa[q]=p; if(q!=p)size[p]+=size[q]; } for(int i=1;i<=n;i++) if(size[i]==1&&i==fa[i]) { if(n!=2)printf("1\n%d\n",i); else {puts("2");puts("1 2");} return 0; } tarjan(1,0); if(tot>1)mark[1]=1; else mark[1]=0; for(int i=1;i<=n;i++) if(!mark[i]&&d[i]-1==m-(n-1)) q[++top]=i; printf("%d\n",top); for(int i=1;i<=top;i++) printf("%d ",q[i]); return 0; } |
计数器 9856383
OI 课件=>
OI 课件=>
表格没加载好……