D. 备用交换机

题目描述

n个城市之间有通讯网络，每个城市都有通讯交换机，直接或间接与其它城市连接。因电子设备容易损坏，需给通讯点配备备用交换机。但备用交换机数量有限，不能全部配备，只能给部分重要城市配置。于是规定：如果某个城市由于交换机损坏，不仅本城市通讯中断，还造成其它城市通讯中断，则配备备用交换机。请你根据城市线路情况，计算需配备备用交换机的城市个数，及需配备备用交换机城市的编号。

输入格式

输入文件有若干行 第一行，一个整数n，表示共有n个城市(2<=n<=100) 下面有若干行,每行2个数a、b，a、b是城市编号，表示a与b之间有直接通讯线路。

输出格式

输出文件有若干行 第一行，1个整数m，表示需m个备用交换机，下面有m行，每行有一个整数，表示需配备交换机的城市编号，输出顺序按编号由小到大。如果没有城市需配备备用交换机则输出0。

样例

样例输入

7
1 2
2 3
2 4
3 4
4 5
4 6
4 7
5 6
6 7

样例输出

2
2
4

数据范围与提示

数据中可能存在森林

#include
#include

namespace bikuhiku{
    template  _T gtr(_T &_compare_x,_T &_compare_y) {
        return _compare_x > _compare_y ? _compare_x : _compare_y;
    }
    template  _T les(_T &_compare_x,_T &_compare_y) {
        return _compare_x < _compare_y ? _compare_x : _compare_y;
    }
    template  void get_int(_T &_data_x) {
        int _signal = 1;
        char _get_c;
        _data_x = 0;
        for(_get_c = getchar();_get_c < '0'||_get_c > '9';_get_c = getchar()) if(_get_c == '-') _signal = -1;
        for(;_get_c >= '0'&&_get_c <= '9';_get_c = getchar()) _data_x = (_data_x<<3)+(_data_x<<1)+(_get_c^48);
        _data_x *= _signal;
        return;
    }
    template  void put_int(_T _data_x) {
        if(_data_x > 9) put_int(_data_x/10);
        putchar((_data_x%10)^48);
        return;
    }
    int _ = 0;
    int _Use = 1;
}//申请一块命名空间；
using namespace bikuhiku;
using namespace std;

const int z = 128;
int m, n, ans;
int s, e;

struct line{
	int t, next;
} edge[z*128];
int cnt, head[z], od[z];
void adline(int &f,int &t) {
	edge[++cnt].next = head[f];
	edge[cnt].t = t;
	head[f] = cnt;
	return;
}

stack stk;
int dfn[z], low[z], time, cvnum;
bool cut_vertex[z];
void tarjan(int &u,int &root) {
	dfn[u] = low[u] = ++time;
	int sub = 0;
	for(int i = head[u];i;i = edge[i].next) {
		if(!dfn[edge[i].t]) {
			++sub;
			tarjan(edge[i].t,root);
			low[u] = les(low[u],low[edge[i].t]);
			if(dfn[u] <= low[edge[i].t]) 
				if(u != root||sub > 1) {
					if(!cut_vertex[u]) ++cvnum;
					cut_vertex[u] = true;
				}
		} else {
			low[u] = les(low[u],dfn[edge[i].t]);
		}
	}
	return;
} 

int main() {
	get_int(n);
	while(scanf("%d %d",&s,&e) != EOF) {
		adline(s,e);
		adline(e,s);
	}
	for(int i = 1;i <= n;++i) 
		if(!dfn[i]) tarjan(i,i);
	put_int(cvnum);
	putchar(10);
	for(int i = 1;i <= n;++i) 
		if(cut_vertex[i]) {
			put_int(i);
			putchar(10);
		}
	return 0^_^0;
}