uoj#67. 新年的毒瘤（割顶）

　　　　　　　　　　　　　　#67. 新年的毒瘤

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

这个长着毒瘤的树可以用n个结点m 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。

现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。

样例一

input

6 6

1 2

1 3

2 4

2 5

4 6

5 6

output

3

4 5 6

256MB

来源

UOJ Goodbye Jiawu

【思路】

无向图的割顶。

如果剩下的点组成一棵树，则满足边数为n-2。

　　 那么“毒瘤”满足：1/非割顶；2/度数=m-(n-2)。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<iostream>

 using namespace std;

 const int maxn = +;

 int pre[maxn],low[maxn],iscut[maxn],dfs_clock;

 vector<int> G[maxn];

 int dfs(int u,int fa) {

     int lowu=pre[u]=++dfs_clock;

     int ch=;

     for(int i=;i<G[u].size();i++) {

         int v=G[u][i];

         if(!pre[v]) {

             ch++;

             int lowv=dfs(v,u);

             lowu=min(lowu,lowv);

             if(lowv>=pre[u]) iscut[u]=;    //只要有一个

         }

         else if(pre[v]<pre[u] && v!=fa) {

             lowu=min(lowu,pre[v]);

         }

     }

     if(fa< && ch==) iscut[u]=;

     low[u]=lowu;

     return lowu;

 }

 int read() {

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     int x=;

     while(isdigit(c))

         x=x*+c-'' , c=getchar();

     return x;

 }

 int n,m;

 int d[maxn],ans[maxn];

 int main() {

     n=read(),m=read();

     int u,v;

     for(int i=;i<m;i++) {

         u=read(),v=read();

         u--,v--;

         d[u]++,d[v]++;

         G[u].push_back(v),G[v].push_back(u);

     }

     dfs(,-);

     int tot=;

     for(int i=;i<n;i++)

         if(!iscut[i] && d[i]==m-(n-))

             ans[tot++]=i+;

     printf("%d\n",tot);

     for(int i=;i<tot;i++) printf("%d ",ans[i]);

     return ;

 }