JZOJ 4679【NOIP2016提高A组8.11】种树

Description

The Solution

首先明确树的概念：我们可以理解成，有n−1 条边的无向连通图

“有 n−1 条边”提示我们最终图里有 n−2条边，所以你需要删一个度数为 m−(n−2)的结点。

因为删掉这个点后剩下的图仍然连通，所以这个点不能是割点。

用 Tarjan 算法求割点，然后输出所有不是割点且度数满足条件的结点就行了。

Code

#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #define fo(i,a,b) for (int i=a;i<=b;i++) #define fd(i,a,b) for (int i=a;i>=b;i--) #define N 100005 using namespace std; int t[N*2],next[N*2],last[N*2],l=0,n,m; int rd[N],a[N],dfn[N],low[N],tot=0; bool bz[N],v[N]; inline int read() { int x=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*w; } void add(int x,int y) { t[++l]=y; next[l]=last[x]; last[x]=l; } void Tarjan(int x) { low[x]=dfn[x]=++tot; int k=last[x]; v[x]=true; while (k) { if (!dfn[t[k]]) { Tarjan(t[k]); low[x]=min(low[x],low[t[k]]); if (low[t[k]]>=dfn[x]) bz[x]=true; } else if (v[t[k]] && dfn[t[k]]<low[x]) low[x]=dfn[t[k]]; k=next[k]; } } int main() { n=read();m=read(); fo(i,1,m) { int x,y; x=read();y=read(); add(x,y);add(y,x); rd[x]++,rd[y]++; } fo(i,1,n) if (rd[i] && !v[i]) Tarjan(i); fo(i,1,n) if (!bz[i] && (n-2==m-rd[i])) a[++a[0]]=i; printf("%d\n",a[0]); fo(i,1,a[0]) printf("%d ",a[i]); return 0; }