tarjan求割点:cojs 8. 备用交换机
★★ 输入文件:gd.in
输出文件:gd.out
简单对比
时间限制:1 s 内存限制:128 MB
- 【问题描述】
n个城市之间有通讯网络,每个城市都有通讯交换机,直接或间接与其它城市连接。因电子设备容易损坏,需给通讯点配备备用交换机。但备用交换机数量有限,不能全部配备,只能给部分重要城市配置。于是规定:如果某个城市由于交换机损坏,不仅本城市通讯中断,还造成其它城市通讯中断,则配备备用交换机。请你根据城市线路情况,计算需配备备用交换机的城市个数,及需配备备用交换机城市的编号。
【输入格式】
输入文件有若干行
第一行,一个整数n,表示共有n个城市(2<=n<=100)
下面有若干行,每行2个数a、b,a、b是城市编号,表示a与b之间有直接通讯线路。
第一行,一个整数n,表示共有n个城市(2<=n<=100)
下面有若干行,每行2个数a、b,a、b是城市编号,表示a与b之间有直接通讯线路。
【输出格式】
输出文件有若干行
第一行,1个整数m,表示需m个备用交换机,下面有m行,每行有一个整数,表示需配备交换机的城市编号,输出顺序按编号由小到大。如果没有城市需配备备用交换机则输出0。
第一行,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
#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 ;
}