备用交换机

【题目描述】

在n个城市之间存在着通讯网络，每个城市都配备着通讯交换机，直接地或间接地与其它城市连接，某个城市如果其交换机损坏，不仅本城市通讯会中断，还会造成其它城市通讯中断，则需要配备备用交换机。

现询问需要配备备用交换机的城市的总数，以及需要配备备用交换机的城市的编号。

【输入描述】

第一行输入一个整数n，表示共有n个城市

【输出描述】

第一行输出一个整数m，表示需要m个备用交换机；

接下来m行，每行输出一个整数，表示需要配备备用交换机的城市编号，输出顺序按照编号由小到大，如果没有城市需要配备备用交换机，则输出0。

【输入样例】

1 2

2 3

2 4

3 4

4 5

4 6

4 7

5 6

6 7

【输出样例】

源代码：

#include<cstdio>
#include<vector>
using namespace std;
vector <int> List[10001];
int n,Root,Num(0),Ans(0),i[101],j[101];
bool f[101]={0};
void Add(int t1,int t2)
{
    List[t1].push_back(t2);
    List[t2].push_back(t1);
    return;
}
void Tarjan(int t)
{
    int Sum(0);
    i[t]=j[t]=++Num;
    for (int a=0;a<List[t].size();a++)
    {
        int T=List[t][a];
        if (!j[T])
        {
            Tarjan(T);
            Sum++;
            i[t]=min(i[t],i[T]);
            if ((t==Root&&Sum>1)||(t!=Root&&i[T]>=j[t])) //割点应具备两个条件中的一个：(1)为树根，且具有一个以上的子树(2)不为树根，i[T]>=j[t]。
              if (!f[t])
              {
                Ans++;
                f[t]=true;
              }
        }
        else
          i[t]=min(i[t],j[T]);
    }
    return;
}
int main() //裸Tarjan求割点。
{
    scanf("%d",&n);
    int t1,t2;
    while (scanf("%d%d",&t1,&t2)!=EOF)
      Add(t1,t2);
    for (int a=1;a<=n;a++)
      if (!j[a])
      {
        Root=a;
        printf("%d ",a);
        Tarjan(a);
      }
    printf("%d
",Ans);
    for (int a=1;a<=n;a++)
      if (f[a])
        printf("%d
",a);
    return 0;
}

/*
    Tarjan求割点，若为根节点，如果有两个子树，那么去掉此节点就会导致不连通。
    若不为根节点，其实是不是无所谓，如上，源节点在此节点之下或是此节点，那么去掉此节点就会上下不联通。
*/