UOJ67 新年的毒瘤 Tarjan算法求割点
辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。
这个长着毒瘤的树可以用 $n$ 个结点 $m$ 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。
现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。
输入格式
第一行两个正整数 $n,m$,表示有 $n$ 个点 $m$ 条边。保证 $n \ge 2$。
接下来 $m$ 行,每行两个整数 $v,u$,表示 $v$ 和 $u$ 之间有一条无向边。$1 \le v,u \le n$。保证没有重边和自环。
输出格式
第一行一个正整数 $ns$,表示这个图中有 $ns$ 个结点是毒瘤。
接下来一行,共 $ns$ 个整数,每个整数表示一个毒瘤结点的编号。请按编号从小到大的顺序输出。
数据保证图中至少存在一个毒瘤结点。
题解
树是什么?树是n点n-1边的无向无环连通图。
显然一个点是毒瘤节点的要求是:
- 删了这个点,图是连通的
- 删了这个点,图的边数是点数$-1$
对于第二个要求,设原来有n点m边,则删完以后有$n-1$点$n-2$边,删掉一个度为$m-n+2$的点就好了。
原图不一定是连通的。
如果图不是连通的,那么,,,因为一定有解,所以这个图一定由两个子图构成:一个点和一棵树,也就是$n$点$n-2$边,那个度为$0$的就是毒瘤节点啊。
对于其它情况,图是连通的,那么只要删掉的点不是割点就是满足第一个要求了。
综合这些,我们想到了这样的算法:
如果$m=n-2$,则特判找到度为$0$的点就好了。
否则找到所有的割点,对于每个点,如果它度为$m-n+2$并且不是割点,那么它是一个毒瘤节点。好像很有道理的样子啊。。。。
然而!!!!
对于$m=n-2$的情况,,$m - n + 2 = 0$,,这个度为0的点恰好满足,并且别的点都不满足。
并且,这个子图没有割点,也就是它同样满足两个要求,就不用特判了。
所以正解就找到了:找到所有的割点,对于每个点,如果它度为$m-n+2$并且不是割点,那么它是一个毒瘤节点。
核心代码:
/*
Author: CNYALI_LK
LANG: C++
*/
//宏定义up:
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
void dfs(int x,int fa){//求割点
dfn[x]=low[x]=++tim;
f[x]=fa;
int tot=0,ok=0;
for(int i=beg[x];i;i=lst[i]){//链式前向星
if(!dfn[to[i]]){
++tot;
dfs(to[i],x);
low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>=dfn[x])ok=1;
}
else low[x]=min(low[x],dfn[to[i]]);
}
if((!fa&&tot>1)||(fa&&ok&&tot))gd[x]=1;
}
//main函数重要的代码:
up(i,1,n)if(!dfn[i]){
dfs(i,0);
}
up(i,1,n)if(!gd[i]&&sum[i]==m-n+2)ans[++anss]=i;//sum[i]是i的度
// anss是个数,ans是存储每一个毒瘤节点