题目链接：http://cojs.tk/cogs/problem/problem.php?pid=8
题意：n个城市之间有通讯网络，每个城市都有通讯交换机，直接或间接与其它城市连接。因电子设备容易损坏，需给通讯点配备备用交换机。但备用交换机数量有限，不能全部配备，只能给部分重要城市配置。于是规定：如果某个城市由于交换机损坏，不仅本城市通讯中断，还造成其它城市通讯中断，则配备备用交换机。请你根据城市线路情况，计算需配备备用交换机的城市个数，及需配备备用交换机城市的编号。
分析：无向图求割点。
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 const int N=100+5; 4 struct EDGE{ 5 int v,next; 6 }edge[N*N]; 7 int first[N],low[N],dfn[N]; 8 bool cut[N]; 9 int g,cnt,rt,son,ans; 10 int min(int a,int b) 11 { 12 return a<b?a:b; 13 } 14 void AddEdge(int u,int v) 15 { 16 edge[g].v=v; 17 edge[g].next=first[u]; 18 first[u]=g++; 19 } 20 void Tarjan(int u) 21 { 22 int i,v; 23 low[u]=dfn[u]=++cnt; 24 for(i=first[u];i!=-1;i=edge[i].next) 25 { 26 v=edge[i].v; 27 if(!dfn[v]) 28 { 29 Tarjan(v); 30 if(u==rt) 31 son++; 32 else 33 { 34 low[u]=min(low[u],low[v]); 35 if(low[v]>=dfn[u]&&cut[u]==false) 36 { 37 ans++; 38 cut[u]=true; 39 } 40 } 41 } 42 else 43 low[u]=min(low[u],dfn[v]); 44 } 45 } 46 int main() 47 { 48 freopen("gd.in","r",stdin); 49 freopen("gd.out","w",stdout); 50 int n,u,v,i; 51 scanf("%d",&n); 52 memset(first,-1,sizeof(first)); 53 memset(low,0,sizeof(low)); 54 memset(dfn,0,sizeof(dfn)); 55 memset(cut,false,sizeof(cut)); 56 g=cnt=ans=0; 57 while(scanf("%d%d",&u,&v)!=EOF) 58 { 59 AddEdge(u,v); 60 AddEdge(v,u); 61 } 62 for(i=1;i<=n;i++) 63 { 64 if(!dfn[i]) 65 { 66 rt=i; 67 son=0; 68 Tarjan(i); 69 if(son>1&&cut[i]==false) 70 { 71 cut[i]=true; 72 ans++; 73 } 74 } 75 } 76 printf("%d ",ans); 77 for(i=1;i<=n;i++) 78 if(cut[i]) 79 printf("%d ",i); 80 return 0; 81 }