uoj67
题意:
辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。 这个长着毒瘤的树可以用 n 个结点 m 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。 现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。
输入:
第一行两个正整数 n,m ,表示有 n 个点 m 条边。保证 n≥2 。 接下来 m 行,每行两个整数 v,u ,表示 v 和 u 之间有一条无向边。1≤v,u≤n 。保证没有重边和自环。
辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。 这个长着毒瘤的树可以用 n 个结点 m 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。 现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。
输入:
第一行两个正整数 n,m ,表示有 n 个点 m 条边。保证 n≥2 。 接下来 m 行,每行两个整数 v,u ,表示 v 和 u 之间有一条无向边。1≤v,u≤n 。保证没有重边和自环。
删掉一个点后,也就删掉了与他相连的所有边,记录这些边点条数(点的度数),删掉后成为树的充要条件,剩下n-2条边
且删除的点不是割点。
#include<bits/stdc++.h> using namespace std; struct Graph{ static const int maxn=1e5+5, maxm=3e5+5; struct star{int v,nex;}edge[maxm<<1]; int head[maxn],cnt,n; int d[maxn]; void ini(int n){ this->n=n; cnt=-1; for(int i=0;i<=n;i++) head[i]=-1; } void add_edge(int u,int v){ edge[++cnt]=star{v,head[u]}; head[u]=cnt; edge[++cnt]=star{u,head[v]}; head[v]=cnt; d[u]++; d[v]++; } }; struct Tarjan:Graph{//割点 int low[maxn],dfn[maxn],cut[maxn]; int step; void tarjan(){ step=0; for(int i=0;i<=n;i++) dfn[i]=cut[i]=0; for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快 } void tarjan(int u,int father=0){//此函数不开放 low[u]=dfn[u]=++step; int first=1, son=0; for(int i=head[u];~i;i=edge[i].nex){ int v=edge[i].v; if(v==father&&!first) first=false; else if(dfn[v]) low[u]=min(low[u],dfn[v]); else{ son++; tarjan(v,u); low[u]=min(low[u],low[v]); //一个顶点u是割点,当且仅当1或2 //1.u为树根且u有多与一个子树 //2.u不为树根且存在边(u,v)为树边,使得dfn[u]<=low[v] if(father!=0&&dfn[u]<=low[v]) cut[u]=1; if(father==0&&son>1) cut[u]=1; } } } }graph; inline int read(){ int ret=0,f=1; char ch=getchar(); while('0'>ch||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while('0'<=ch&&ch<='9'){ ret=(ret<<1)+(ret<<3)+(ch^48); ch=getchar(); } return ret; } int main(){ int n=read(); int m=read(); graph.ini(n); for(int i=0;i<m;i++) graph.add_edge(read(),read()); graph.tarjan(); vector<int>ans; for(int i=1;i<=n;i++) { if(!graph.cut[i]&&(m-graph.d[i])==n-2){ ans.push_back(i); } } cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++) { printf("%d", ans[i]); if(i+1==ans.size()) printf("\n"); else printf(" "); } }