备用交换机题解

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

```cpp /* * Problem: 备用交换机 gd * Author: Guo Jiabao * Time: 2009.4.7 15:43 * State: Solved * Memo: 求割顶 */ #include #include #include #include #include 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",&N); while (scanf("%d%d",&a,&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]=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; } ```

http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=8

备用交换机

问题描述

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

【输入格式】

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

【输出格式】

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

【输入输出样例】

输入文件名： gd.in

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

输出文件名：gd.out

2
2
4

上次修改时间 2017-02-03

相关日志