辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。

这个长着毒瘤的树可以用 $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. 删了这个点,图是连通的
  2. 删了这个点,图的边数是点数$-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是存储每一个毒瘤节点

标签: 图论, UOJ

添加新评论