#include<stdio.h> /*我们可以默认站点是全部被破坏的,建立通道时重建这些站点(没有在通道中的站点默认被破坏),这时候破坏站点z,如果u,v不连通,则说明z为关键站点。*/ struct node { int x; }; int n,m,u,v,sum=0; char e[1001][1001]={0},des[1001]={[0 ... 1000]=1}; //默认站点被破坏 void search(); char error_check(); //bfs判断有无通路 int main() { int i; scanf("%d %d",&n,&m); for(i=0;i<m;i++) { scanf("%d %d",&u,&v); e[u][v]=1,e[v][u]=1; des[u]=0,des[v]=0; } scanf("%d %d",&u,&v); if(error_check()) //两点不连通 printf("-1\n"); else { search(); printf("%d\n",sum); } return 0; } void search() { int z; for(z=1;z<=n;z++) { if(z!=u && z!=v && des[z]==0) //逐一寻找站点z { des[z]=1; if(error_check()) sum++; des[z]=0; } } } char error_check() { struct node que[1001]; char book[1001]={0}; int i,head=0,tail=0; que[tail].x=u; book[u]=1; tail++; while(head<tail) { if(des[que[head].x]==0) { for(i=1;i<=n;i++) { if(des[i]==0 && e[que[head].x][i]==1 && book[i]==0) { if(i==v) //此时站点u,v有通路 return 0; book[i]=1; que[tail].x=i; tail++; } } } head++; } return 1; }
0.0分
3 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:579 |
1009题解浏览:720 |
printf基础练习2 (C语言代码)浏览:616 |
a+b浏览:432 |
1054题解浏览:460 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:672 |
母牛的故事 (C语言代码)浏览:478 |
10月月赛题解浏览:536 |
1199题解浏览:653 |
简单的a+b (C语言代码)浏览:508 |