nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

uoj67

题意：
        辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。         这个长着毒瘤的树可以用 n 个结点 m 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。         现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。

输入：
        第一行两个正整数 n,m ，表示有 n 个点 m 条边。保证 n≥2 。 接下来 m 行，每行两个整数 v,u ，表示 v 和 u 之间有一条无向边。1≤v,u≤n 。保证没有重边和自环。

        删掉一个点后，也就删掉了与他相连的所有边，记录这些边点条数（点的度数），删掉后成为树的充要条件，剩下n-2条边 且删除的点不是割点。

#include<bits/stdc++.h>
using namespace std;

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],cnt,n;
    int d[maxn];
    void ini(int n){
        this->n=n; cnt=-1;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add_edge(int u,int v){
        edge[++cnt]=star{v,head[u]}; head[u]=cnt;
        edge[++cnt]=star{u,head[v]}; head[v]=cnt;
        d[u]++;
        d[v]++;
    }
};

struct Tarjan:Graph{//割点
    int low[maxn],dfn[maxn],cut[maxn];
    int step;
    void tarjan(){
        step=0;
        for(int i=0;i<=n;i++) dfn[i]=cut[i]=0;
        for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快
    }
    void tarjan(int u,int father=0){//此函数不开放
        low[u]=dfn[u]=++step;
        int first=1, son=0;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&!first) first=false;
            else if(dfn[v]) low[u]=min(low[u],dfn[v]);
            else{
                son++;
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                //一个顶点u是割点,当且仅当1或2
                //1.u为树根且u有多与一个子树
                //2.u不为树根且存在边(u,v)为树边，使得dfn[u]<=low[v]
                if(father!=0&&dfn[u]<=low[v]) cut[u]=1;
                if(father==0&&son>1) cut[u]=1;
            }
        }
    }
}graph;

inline int read(){
    int ret=0,f=1;
    char ch=getchar();
    while('0'>ch||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9'){
        ret=(ret<<1)+(ret<<3)+(ch^48);
        ch=getchar();
    }
    return ret;
}

int main(){
    int n=read();
    int m=read();
    graph.ini(n);
    for(int i=0;i<m;i++) graph.add_edge(read(),read());

    graph.tarjan();

    vector<int>ans;

    for(int i=1;i<=n;i++) {
        if(!graph.cut[i]&&(m-graph.d[i])==n-2){
            ans.push_back(i);
        }
    }

    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) {
        printf("%d", ans[i]);
        if(i+1==ans.size()) printf("\n");
        else printf(" ");
    }


}