Description
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数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)。
接下来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[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int getval() { int ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; 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,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); memset(path,0,sizeof(path)); memset(G,0,sizeof(G)); ans=0; } void dfs(int cur,int len) { if(cur==f) { ans++; for(int i=1;i<len;i++) cnt[path[i]]++; return ; } for(int i=1;i<=n;i++) { if(G[cur][i]&&vis[i]==0) { vis[i]=1; path[len]=i; dfs(i,len+1); vis[i]=0; } } } int main() { int x,y; scanf("%d %d",&n,&m); init(); for(int i=1;i<=m;i++) { scanf("%d %d",&x,&y); G[x][y]=G[y][x]=1; } scanf("%d %d",&s,&f); vis[s]=1; path[1]=s; dfs(s,2); if(ans==0) { printf("-1 "); return 0; } int sum=0; for(int i=1;i<=n;i++) if(cnt[i]==ans) sum++; printf("%d ",sum-2); return 0; } /* 求关于两个点的割点 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[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int getval() { int ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; 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=1;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=1;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 0; else return 1; } int main() { int x,y; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d %d",&x,&y); a[i]=x; b[i]=y; } scanf("%d %d",&s,&f); int sum=0; for(int i=1;i<=n;i++) { if(i==s||i==f) continue; if(fun(i)==0) sum++; } printf("%d ",sum); return 0; } /* 无向图求关于某两点的割点个数 遍历每个点，进行多次并查集操作，如果去除和某个点有关的所有边 导致起点和终点不能连通，那么该点属于关于这两点的割点 该方法属于暴力法 */