题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。 两个空间站间可能直接通信,也可能通过其它空间站中转。
对于两个站点x和y (x != y), 如果能找到一个站点z,使得: 当z被破坏后,x和y无法通信,则称z为关于x,y的关键站点。
显然,对于给定的两个站点,关于它们的关键点的个数越多,通信风险越大。
你的任务是:已知网络结构,求两站点之间的通信风险度,即:它们之间的关键点的个数。
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数,链路数。 空间站的编号从1到n。通信链路用其两端的站点编号表示。 接下来m行,每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。 最后1行,两个数u,v,代表被询问通信风险度的两个站点。
输出:一个整数,如果询问的两点不连通则输出-1.
例如: 用户输入: 7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6 则程序应该输出: 2 初次看到这个题,一下想到邻接矩阵,然后通过深度搜索找寻答案
#include<iostream>
#include<queue>
#define N 1000
using namespace std;
int num[N][N] = {0};
int map[N] = {0};
int time[N] = {0};
int x[N] = {0};
int u,v ,n,m,cnt = 0;
//构建矩阵
void creat(int n,int m)
{
int u , v;
for(int i = 0; i < m; i++)
{
cin >> u>>v;
num[u][v] = 1;
num[v][u] = 1;
}
cout<<"所建立的矩阵为:"<<endl;
for(int i = 1; i <= n; i++)
{
for(int j = 1;j <= n; j++)
{
cout << num[i][j];
}
cout << endl;
}
return ;
}
//判断是否走回路
int check(int n,int step)
{
for(int i = 0;i <= step; i++)
{
if(n==map[i])
{
return 0;
}
}
return 1;
}
//矩阵搜索 DFS
void DFS(int index,int step)
{
if(index==v)
{
cnt++;
for(int i = 0; i < step;i++)
{
time[map[i]]++;
}
return ;
}
for(int i = 1; i <= n; i++)
{
if(num[index][i]&&check(i,step))
{
map[step] = i;
DFS(i,step+1);
map[step] = 0;
}
}
}
int main()
{
cin >> n>>m;
creat(n,m);
cin >> u >> v;
map[0] = u;
DFS(u,1);
int x = 0;
for(int i = 1; i <= n; i++)
{
if(time[i]==cnt)//判读在某个站点是否是唯一数
{
x++;
}
}
if(cnt==0)
{
cout << "-1";
}
else if(x==0)
{
cout << "0";
}
else
{
cout << x-2;
}
return 0;
}
之后查了一下其他算法,发现使用并查集特别方便。 详细了解并查集请见并查集
//并查集
#include<iostream>
using namespace std;
int pre[1005];//每个点的前导点
int route[2005][2];
//可以配对的路线
int sum = 0;
//符合条件的 即关键点的数量
//查找
int find(int x)
{
int r = x;
while (pre[r] != r)
r = pre[r];
int i = x, j;
while (i != r)//路径压缩算法
{
j = pre[i];//在改变他的前导点时,存储他的值
pre[i] = r;
i = j;//改变他的前导点为根节点
}
return r;
}
void join(int x, int y)
//组合
{
int fx = find(x), fy = find(y);//分别记录x,y的根节点
if (fx != fy)//如果他们的根节点相同,则说明他们不是连通图
pre[fx] = fy;//将x的根结点 同 相连接
}
int main()
{
int n, m;
cin >> n>>m;//n表示站点的个数,m表示链路的个数
for (int i = 0; i < m; i++)
{
cin >> route[i][0] >> route[i][1];
join(route[i][0], route[i][1]);//将数据相互连接
}
int q1,q2;//待询问的两个点
cin >> q1 >> q2;
for (int ii = 0; ii < n; ii++)pre[ii] = ii;
for (int j = 0; j < m; j++)
{
join(route[j][0], route[j][1]);
}
int a = find(q1);
int b = find(q2);
//如果边全部存在时不可达,则输出 -1;
if (a != b)
{
cout << "-1" << endl;
}
else
{
for (int i = 1; i <= n; i++)
//枚举每一个点
{
if (i == q1 || i == q2)continue;
//如果是被询问的点,跳过,无需遍历 此处是最关键的部分
for (int j = 1; j <= n; j++)pre[j] = j;
//将每一个初始化
for (int j = 0; j < m; j++)
{
if (route[j][0] == i || route[j][1]==i)continue;
//去除当前点互相关联的边 解决问题的关键
int a = find(route[j][0]);
int b = find(route[j][1]);
if (a > b) { a ^= b; b ^= a; a ^= b; };//交换
if (a != b)pre[b] = a;
//以较小的点作为父节点
}
int a = find(q1);
int b = find(q2);
if (a != b)sum++;;
}