tarjan求割点：cojs 8. 备用交换机

★★ 输入文件：gd.in 输出文件：gd.out 简单对比
时间限制：1 s 内存限制：128 MB

【问题描述】

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

【输入格式】

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

【输出格式】

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

【输入输出样例】

输入文件名： gd.in

1 2

2 3

2 4

3 4

4 5

4 6

4 7

5 6

6 7

输出文件名：gd.out

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #include<cstring>

 #define N 102

 int low[N],dfn[N],root,topt=,n,a,b,ans[N];

 bool is_gd[N];

 struct Edge{

     int v,last;

 }edge[N*N*];

 int head[N],t=;

 void add_edge(int u,int v)

 {

     ++t;

     edge[t].v=v;

     edge[t].last=head[u];

     head[u]=t;

 }

 void input()

 {

     scanf("%d",&n);

     while(scanf("%d%d",&a,&b)==)

     {

         add_edge(a,b);

         add_edge(b,a);

     }

 }

 void tarjan(int k)

 {/*记住这个模板就好了*/

     int cnt=;

     dfn[k]=low[k]=++topt;

     for(int l=head[k];l;l=edge[l].last)

     {

         int v=edge[l].v;

         if(!dfn[v])

         {

             tarjan(v);

             ++cnt;

             low[k]=min(low[k],low[v]);

             if((root==k&&cnt>)||(root!=k&&low[v]>=dfn[k]))

               is_gd[k]=true;

         }

         else low[k]=min(low[k],dfn[v]);

     }

 }

 int main()

 {

     freopen("gd.in","r",stdin);

     freopen("gd.out","w",stdout);

     input();

     root=;

     tarjan();

     for(int i=;i<=n;++i)

       if(is_gd[i])

       ans[++ans[]]=i;

     printf("%d\n",ans[]);

     for(int i=;i<=ans[];++i)

       printf("%d\n",ans[i]);

     fclose(stdin);fclose(stdout);

     return ;

 }

秒客网

tarjan算法求割点cojs 8

tarjan求割点：cojs 8. 备用交换机

相关文章