UOJ#67 新年的毒瘤

Captain_Paul

2018-11-07 16:28:38

Personal

题意:一个无向图,如果删除一个点之后剩下的图是一棵树,那么这个点是毒瘤点,问哪些点是毒瘤点 ------------ - 删除一个点之后,剩下$n-1$个点构成的树有$n-2$条边,所以毒瘤点的度数一定是$m-n+2$ - 树是连通图,所以毒瘤点一定不是图的割点 $tarjan$求出割点之后判断即可 ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=1e5+5; struct node { int to,nxt; }edge[N<<1]; int n,m,num,ans,head[N],d[N],fa[N],dfn[N],low[N],tim,cut[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; ++d[to]; } void tarjan(int k) { dfn[k]=low[k]=++tim; int cnt=0; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!dfn[v]) { fa[v]=fa[k]; tarjan(v); low[k]=min(low[k],low[v]); if (low[v]>=dfn[k]&&k!=fa[k]) cut[k]=1; if (k==fa[k]) ++cnt; } low[k]=min(low[k],dfn[v]); } if (k==fa[k]&&cnt>1) cut[k]=1; } int main() { n=read(),m=read(); for (reg int i=1;i<=m;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } for (reg int i=1;i<=n;i++) fa[i]=i; for (reg int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); for (reg int i=1;i<=n;i++) if (d[i]==m-n+2&&!cut[i]) ++ans; printf("%d\n",ans); for (reg int i=1;i<=n;i++) if (d[i]==m-n+2&&!cut[i]) printf("%d ",i); return 0; } ```