首页 > 代码库 > 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. 新年的毒瘤