【问题描述】

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

思路：

如果一台交换机损坏使得原图不连通，则此交换机是原图中的一个割点

详见

然后就是找割点并输出

人生第一次用markdown，感觉还不错

源代码/pas:

type  edge=record    opp,y,next:longint;    visit:boolean;  end;var  e:array[1..1000]of edge;  dfn,low,ls:array[1..1000]of longint;  ans:array[1..1000]of boolean;  n,m,maxE,t,num:longint;procedure add(x,y:longint);begin  inc(maxE);  e[maxE].y:=y;  e[maxE].opp:=maxE+1;  e[maxE].next:=ls[x];  ls[x]:=maxE;  inc(maxE);  e[maxE].y:=x;  e[maxE].opp:=maxE-1;  e[maxE].next:=ls[y];  ls[y]:=maxE;end;function min(x,y:longint):longint;begin  min:=x;  if y
     
      0 do  with e[i] do  begin    if not visit then    begin      visit:=true;      e[opp].visit:=true;      if dfn[y]=0 then      begin        if x=1 then inc(num);        tarjan(y);        low[x]:=min(low[y],low[x]);        if low[y]>=dfn[x] then        ans[x]:=true;      end      else      low[x]:=min(low[x],dfn[y]);    end;    i:=next;  end;end;procedure print;var  i:longint;begin  ans[1]:=false;  if num>=2 then ans[1]:=true;  num:=0;  for i:=1 to n do  if ans[i] then inc(num);  writeln(num);  for i:=1 to n do  if ans[i] then writeln(i);end;procedure init;var  i,x,y:longint;begin  readln(n);  while not eof do  begin    readln(x,y);    add(x,y);  end;end;begin  assign(input,'gd.in');  assign(output,'gd.out');  reset(input);  rewrite(output);  init;  tarjan(1);  print;  close(input);  close(output);end.