首页 > 代码库 > UOJ #67. 新年的毒瘤
UOJ #67. 新年的毒瘤
Description
给你一个无向图,求删掉一个点及其连的边后,剩下的图是树结构,求这些点.
Sol
Tarjan求割点.
只需要求出割点,因为删掉的点只需要满足:不是割点(保证连通),边数位m-(n-2),即可.
PS:Tarjan求割点的时候对于根要计算是他子树的点,而不是他的度数.
Code
#include<cstdio>#include<vector>#include<iostream>using namespace std;const int N = 100005;#define debug(a) cout<<#a<<"="<<a<<" "int n,m,cnt,ans;vector<int> g[N];int b[N],out[N],du[N];int dfsn[N],low[N];inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }void Tarjan(int u,int fa){ dfsn[u]=low[u]=++cnt;int c=0; for(int i=0,v;i<du[u];i++) if((v=g[u][i])!=fa){ if(!dfsn[v]){ Tarjan(v,u),low[u]=min(low[u],low[v]),c++; if(fa>0&&dfsn[u]<=low[v]) b[u]=1; }else low[u]=min(low[u],dfsn[v]); }if(fa==0&&c>1) b[u]=1;}int main(){// freopen("in.in","r",stdin); n=in(),m=in(); for(int i=1,u,v;i<=m;i++) u=in(),v=in(),du[u]++,du[v]++,g[u].push_back(v),g[v].push_back(u); for(int i=1;i<=n;i++) if(!dfsn[i]) Tarjan(i,0); // for(int i=1;i<=n;i++) debug(g[i].size()),debug(low[i]),debug(dfsn[i])<<endl; for(int i=1;i<=n;i++) if(du[i]==m-n+2&&!b[i]) out[++ans]=i; printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d ",out[i]);putchar(‘\n‘); return 0;}
UOJ #67. 新年的毒瘤
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。