Beyond the Void
BYVoid
備用交換機 題解
本文正體字版由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; } ```
備用交換機
問題描述
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

相關日誌