rain


私信TA

用户名:p1317994

访问量:5751

签 名:

(¬_¬)

等  级
排  名 10305
经  验 1023
参赛次数 1
文章发表 2
年  龄 20
在职情况 学生
学  校
专  业

  自我简介:

#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 人评分

  评论区