http://www.cogs.pro/cogs/problem/problem.php?pid=8

★★?? 輸入文件：gd.in?? 輸出文件：gd.out???簡單對比
時間限制：1 s?? 內(nèi)存限制：128 MB

?

n個城市之間有通訊網(wǎng)絡，每個城市都有通訊交換機，直接或間接與其它城市連接。因電子設備容易損壞，需給通訊點配備備用交換機。但備用交換機數(shù)量有限，不能全部配備，只能給部分重要城市配置。于是規(guī)定：如果某個城市由于交換機損壞，不僅本城市通訊中斷，還造成其它城市通訊中斷，則配備備用交換機。請你根據(jù)城市線路情況，計算需配備備用交換機的城市個數(shù)，及需配備備用交換機城市的編號。 【輸入格式】 輸入文件有若干行
第一行，一個整數(shù)n，表示共有n個城市(2<=n<=100)
下面有若干行,每行2個數(shù)a、b，a、b是城市編號，表示a與b之間有直接通訊線路。 【輸出格式】 輸出文件有若干行
第一行，1個整數(shù)m，表示需m個備用交換機，下面有m行，每行有一個整數(shù)，表示需配備交換機的城市編號，輸出順序按編號由小到大。如果沒有城市需配備備用交換機則輸出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

?

Tarjan割點模板

1 #include<algorithm> 2 #include<cstring> 3 #include<cstdio> 4 #define N 1100 5 using namespace std; 6 int n,x,y,tim,tot=1,ans; 7 int dfn[N],low[N],head[N],cut_point[N]; 8 int read() 9 { 10 int x=0,f=1; char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 13 return x*f; 14 } 15 struct Edge 16 { 17 int to,from,next; 18 }edge[N]; 19 int add(int x,int y) 20 { 21 tot++; 22 edge[tot].to=y; 23 edge[tot].next=head[x]; 24 head[x]=tot; 25 } 26 int tarjan(int now,int pre) 27 { 28 int sum=0;bool if_point=false; 29 dfn[now]=low[now]=++tim; 30 for(int i=head[now];i;i=edge[i].next) 31 { 32 int t=edge[i].to; 33 if((i^1)==pre) continue; 34 if(!dfn[t]) 35 { 36 sum++,tarjan(t,i); 37 low[now]=min(low[now],low[t]); 38 if(dfn[now]<=low[t]) if_point=true; 39 } 40 else low[now]=min(low[now],dfn[t]); 41 } 42 if(!pre){if(sum>1) ans++,cut_point[now]=true;} 43 else if(if_point) ans++,cut_point[now]=true; 44 } 45 int main() 46 { 47 freopen("gd.in","r",stdin); 48 freopen("gd.out","w",stdout); 49 50 n=read(); 51 while(scanf("%d%d",&x,&y)==2) 52 add(x,y),add(y,x); 53 for(int i=1;i<=n;i++) 54 if(!dfn[i]) tarjan(i,0); 55 printf("%d\n",ans); 56 for(int i=1;i<=n;i++) 57 if(cut_point[i]) printf("%d\n",i); 58 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Shy-key/p/7413721.html

總結(jié)

以上是生活随笔為你收集整理的COGS——T 8. 备用交换机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。