首页 > 代码库 > 备用交换机（cogs 8）

备用交换机（cogs 8）

2024-08-12 01:36:56   220人阅读

【问题描述】

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

 

技术分享
/*  tarjan求割点  dfs一边，满足下面两种情况之一的节点就是割点  ①v是根节点，并且它有超过两个子节点。  ②v不是叶子节点，并且v的子节点w没有返祖边（即low[w]>=dfs[v]）*/#include<iostream>#include<cstdio>#define M 110using namespace std;int num[M],low[M],s[M*2],instack[M],vis[M],top,indexx;int ok[M],head[M],tot,c1,n,m,cnt;struct node{    int v,pre;};node e[M*M*2];void add(int x,int y){    cnt++;    e[cnt].v=y;    e[cnt].pre=head[x];    head[x]=cnt;}void tarjan(int v){    num[v]=low[v]=++indexx;    instack[v]=vis[v]=1;    s[++top]=v;    for(int i=head[v];i;i=e[i].pre)    {        int w=e[i].v;        if(!vis[w])        {            if(v==1)c1++;            tarjan(w);            low[v]=min(low[w],low[v]);            if(v!=1&&low[w]>=num[v])ok[v]=1;        }        else if(instack[w])          low[v]=min(num[w],low[v]);    }}int main(){    freopen("gd.in","r",stdin);    freopen("gd.out","w",stdout);    scanf("%d",&n);    int x,y;    while(scanf("%d%d",&x,&y)!=EOF)    {        add(x,y);add(y,x);    }    tarjan(1);    if(c1>=2)ok[1]=1;    for(int i=1;i<=n;i++)      if(ok[i])      {          printf("%d\n",i);        break;      }    return 0;}
View Code

 

备用交换机（cogs 8）


联系
我们