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. 删了这个点，图是连通的 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是存储每一个毒瘤节点