備用交換機題解

本文正體字版由OpenCC轉換

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

相關日誌