This post is written in Chinese. Please consider using Google Translate

求无向连通图的割顶，直接DFS求出，按顺序输出即可。

/*
 * Problem: 备用交换机 gd
 * Author: Guo Jiabao
 * Time: 2009.4.7 15:43
 * State: Solved
 * Memo: 求割顶
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101;
using namespace std;
struct edge
{
    edge *next;
    int t;
};
edge *V[MAXN];
int N,D,DFS[MAXN],LOW[MAXN],PAR[MAXN];
bool isgd[MAXN];
inline void addedge(int a,int b)
{
    edge e={V[a],b};
    V[a]=new edge(e);
}
void init()
{
    int a,b;
    freopen("gd.in","r",stdin);
    freopen("gd.out","w",stdout);
    scanf("%d",&#038;N);
    while (scanf("%d%d",&#038;a,&#038;b)!=EOF)
    {
        addedge(a,b);
        addedge(b,a);
    }
}
void dfs(int u,int p)
{
    DFS[u]=LOW[u]=++D;
    PAR[u]=p;
    for (edge *k=V[u];k;k=k->next)
    {
        int v=k->t;
        if (!DFS[v]) //树枝边
        {
            dfs(v,u);
            if (LOW[v]<LOW[u])
                LOW[u]=LOW[v];
        }
        else if (v!=p &#038;& DFS[v]<LOW[u]) //后向边
            LOW[u]=DFS[v];
    }
}
void solve()
{
    int i,u,v,rc=0,gdc=0;
    dfs(1,0);
    for (v=2;v<=N;v++)
    {
        u=PAR[v];
        if (u==1)
            rc++;
        else if (DFS[u]<=LOW[v])
            isgd[u]=true;
    }
    if (rc>=2)
        isgd[1]=true;
    for (i=1;i<=N;i++)
        if (isgd[i])
            gdc++;
    printf("%dn",gdc);
    for (i=1;i<=N;i++)
        if (isgd[i])
            printf("%dn",i);
}
int main()
{
    init();
    solve();
    return 0;
}

<div class="MainText">
<div><a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=8" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=8</a></div>
<div><strong>备用交换机</strong></div>
<div><strong>问题描述</strong></div>
<div>n个城市之间有通讯网络，每个城市都有通讯交换机，直接或间接与其它城市连接。因电子设备容易损坏，需给通讯点配备备用交换机。但备用 交换机数量有限，不能全部配备，只能给部分重要城市配置。于是规定：如果某个城市由于交换机损坏，不仅本城市通讯中断，还造成其它城市通讯中断，则配备备 用交换机。请你根据城市线路情况，计算需配备备用交换机的城市个数，及需配备备用交换机城市的编号。</div>
<div>【输入格式】</div>
<div>输入文件有若干行<br />
第一行，一个整数n，表示共有n个城市(2&lt;=n&lt;=100)<br />
下面有若干行,每行2个数a、b，a、b是城市编号，表示a与b之间有直接通讯线路。</div>
<div>【输出格式】</div>
<div>输出文件有若干行<br />
第一行，1个整数m，表示需m个备用交换机，下面有m行，每行有一个整数，表示需配备交换机的城市编号，<span>输出顺序按编号由小到大。如果没有城市需配备备用交换机则输出0。</span></div>
<div>【输入输出样例】</div>
<div>输入文件名： gd.in</div>
<div>7<br />
1 2<br />
2 3<br />
2 4<br />
3 4<br />
4 5<br />
4 6<br />
4 7<br />
5 6<br />
6 7</div>
<div>输出文件名：<span>gd.out</span></div>
<div>2<br />
2<br />
4</div>
</div>