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
那么该点一定是关于目标两点的割点
dfs爆搜，找到这两点间的所有路径数目ans，如果在1这些路径中，某些点出现的次数是ans
那么该点一定是关于目标两点的割点
具体做法：
搜索路径，记录路径中每个结点的出现次数，最后与可行路径数比较
搜索路径，记录路径中每个结点的出现次数，最后与可行路径数比较
将目标两点设置为起点s和终点f，dfs爆搜其路径
边搜边记录其路径，搜到终点之后，将记录的路径的结点出现次数加1
如果在全部搜索完之后，有点在所有可行路径中出现的次数等于可行路径数，那么该点是关于起点和终点和割点
边搜边记录其路径，搜到终点之后，将记录的路径的结点出现次数加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 ;
}
/*
无向图求关于某两点的割点个数
遍历每个点，进行多次并查集操作，如果去除和某个点有关的所有边
导致起点和终点不能连通，那么该点属于关于这两点的割点
该方法属于暴力法
*/