蓝桥杯历届试题 危险系数（dfs或者并查集求无向图关于两点的割点个数）

时间：2022-01-01 13:17:12

Description

抗日战争时期，冀中平原的地道战曾发挥重要作用。

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数DF(x,y)：

对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

Input

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；

接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；

最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

Output

一个整数，如果询问的两点不连通则输出-1.

Sample Input

7 6

1 3

2 3

3 4

3 5

4 5

5 6

1 6

Sample Output

2

Source

蓝桥杯
 
解法1：DFS
求关于两个点的割点
dfs爆搜，找到这两点间的所有路径数目ans，如果在1这些路径中，某些点出现的次数是ans
那么该点一定是关于目标两点的割点
具体做法：
搜索路径，记录路径中每个结点的出现次数，最后与可行路径数比较
将目标两点设置为起点s和终点f，dfs爆搜其路径
边搜边记录其路径，搜到终点之后，将记录的路径的结点出现次数加1
如果在全部搜索完之后，有点在所有可行路径中出现的次数等于可行路径数，那么该点是关于起点和终点和割点
 
#include<stdio.h>

#include<iostream>

#include<math.h>

#include<string.h>

#include<set>

#include<map>

#include<list>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long LL;

int mon1[]= {,,,,,,,,,,,,};

int mon2[]= {,,,,,,,,,,,,};

int dir[][]= {{,},{,-},{,},{-,}};

int getval()

{

    int ret();

    char c;

    while((c=getchar())==' '||c=='\n'||c=='\r');

    ret=c-'';

    while((c=getchar())!=' '&&c!='\n'&&c!='\r')

        ret=ret*+c-'';

    return ret;

}

#define max_v 1005

int vis[max_v];

int cnt[max_v];

int path[max_v];

int G[max_v][max_v];

int n,m;

int ans;

int s,f;

void init()

{

    memset(vis,,sizeof(vis));

    memset(cnt,,sizeof(cnt));

    memset(path,,sizeof(path));

    memset(G,,sizeof(G));

    ans=;

}

void dfs(int cur,int len)

{

    if(cur==f)

    {

        ans++;

        for(int i=;i<len;i++)

            cnt[path[i]]++;

        return ;

    }

    for(int i=;i<=n;i++)

    {

        if(G[cur][i]&&vis[i]==)

        {

           vis[i]=;

           path[len]=i;

           dfs(i,len+);

           vis[i]=;

        }

    }

}

int main()

{

    int x,y;

    scanf("%d %d",&n,&m);

    init();

    for(int i=;i<=m;i++)

    {

        scanf("%d %d",&x,&y);

        G[x][y]=G[y][x]=;

    }

    scanf("%d %d",&s,&f);

    vis[s]=;

    path[]=s;

    dfs(s,);

    if(ans==)

    {

        printf("-1\n");

        return ;

    }

    int sum=;

    for(int i=;i<=n;i++)

        if(cnt[i]==ans)

           sum++;

    printf("%d\n",sum-);

    return ;

}

/*

求关于两个点的割点

dfs爆搜，找到这两点间的所有路径数目ans，如果在1这些路径中，某些点出现的次数是ans

那么该点一定是关于目标两点的割点

具体做法：

搜索路径，记录路径中每个结点的出现次数，最后与可行路径数比较

将目标两点设置为起点s和终点f，dfs爆搜其路径

边搜边记录其路径，搜到终点之后，将记录的路径的结点出现次数加1

如果在全部搜索完之后，有点在所有可行路径中出现的次数等于可行路径数，那么该点是关于起点和终点和割点

*/

解法二：并查集

无向图求关于某两点的割点个数
遍历每个点，进行多次并查集操作，如果去除和某个点有关的所有边
导致起点和终点不能连通，那么该点属于关于这两点的割点
该方法属于暴力法

#include<stdio.h>

#include<iostream>

#include<math.h>

#include<string.h>

#include<set>

#include<map>

#include<list>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long LL;

int mon1[]= {,,,,,,,,,,,,};

int mon2[]= {,,,,,,,,,,,,};

int dir[][]= {{,},{,-},{,},{-,}};

int getval()

{

    int ret();

    char c;

    while((c=getchar())==' '||c=='\n'||c=='\r');

    ret=c-'';

    while((c=getchar())!=' '&&c!='\n'&&c!='\r')

        ret=ret*+c-'';

    return ret;

}

#define max_v 1005

int pa[max_v];

int n,m;

int a[max_v],b[max_v];

int s,f;

void init()

{

    for(int i=;i<=n;i++)

        pa[i]=i;

}

int find_set(int x)

{

    if(x!=pa[x])

        pa[x]=find_set(pa[x]);

    return pa[x];

}

void union_set(int x,int y)

{

    x=find_set(x);

    y=find_set(y);

    if(x==y)

        return ;

    pa[x]=y;

}

int fun(int v)

{

    init();

    for(int i=;i<=m;i++)

    {

        if(a[i]==v||b[i]==v)

            continue;

        union_set(a[i],b[i]);

    }

    if(find_set(s)!=find_set(f))

        return ;

    else

        return ;

}

int main()

{

    int x,y;

    scanf("%d %d",&n,&m);

    for(int i=;i<=m;i++)

    {

        scanf("%d %d",&x,&y);

        a[i]=x;

        b[i]=y;

    }

    scanf("%d %d",&s,&f);

    int sum=;

    for(int i=;i<=n;i++)

    {

        if(i==s||i==f)

            continue;

       if(fun(i)==)

        sum++;

    }

    printf("%d\n",sum);

    return ;

}

/*

无向图求关于某两点的割点个数

遍历每个点，进行多次并查集操作，如果去除和某个点有关的所有边

导致起点和终点不能连通，那么该点属于关于这两点的割点

该方法属于暴力法

*/

相关文章