求無向連通圖的割頂，直接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>