【FLOYD+并查集】蓝桥杯算法提高 Degrees of Separation
目录
题目详情:
问题描述：
输入说明：
输出说明:
测试用例:
输入：
输出：
题解：
问题分析：
问题1：
问题2：
问题3：
问题4：
题解代码：
Code详细解释：
1. 全局变量与数据结构
2. 并查集操作
3. 初始化函数 init()
4. 节点映射与边处理
5.连通性检测
6.Floyd算法
7.最大分离度计算
题目详情:
问题描述：
在我们联系日益紧密的世界里，人们推测每个人和其他人的分离度不超过六（六度分离）。在这个问题里，你需要写一个程序来找出人们的关系网络中最大的分离度。
对于任意两个人，他们的分离度是联系两个人需要经过的最小的关系数。对于一个关系网络，最大的分离度是网络中任意两人的分离度的最大值。如果一个网络中有两个人没有通过关系链连接起来，这个网络是不连通的。
输入说明：
输入包含多组描述关系网络的数据，对于每组数据，第一行有两个数P，表示网络中人的数目，和R，关系的对数。接下来一行是R个关系。每个关系用两个字符串表示，代表网络中有关系的两个人的名字。每个名字是不同的，并且中间没有空格。因为一个人可能和多个人有联系，一个名字可能在一组数据中出现多次。
最后以一行两个0表示结束。
2<=P<=50，R>=1
输出说明:
对于每个网络，输出网络中最大的分离度。如果这个网络是不连通的，输出DISCONNECTED。每一个网络输出后再输出一个回车。按照样例输出中的格式输出。
测试用例:
输入：
4 4
Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun
4 2
Ashok Chun Ursala Kiyoshi
6 5
Bubba Cooter Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun
0 0
输出：
Network 1: 2
Network 2: DISCONNECTED
Network 3: DISCONNECTED
题解：
问题分析：
问题描述的比较抽象，直接用图来理解。一个关系网络就是一个图，两个人之间的分离度就是两个人之间路径的长度 这是一个不带权图 或者理解为权值等于1也行。题目要求的就是求一个图中 任意两个人的最短路径的最大值，前提是这个图是连通图。如果不是连通图，就输出DISCONNECTED。
我们要解决三个问题：
问题1：
如何判断是否是连通图 我们用并查集实现
参考我的文章：并查集的学习
问题2：
求两个人之间的最短路径 也就是分离度 用FLOYD算法实现 然后遍历一遍DIS数组找最大值即可
参考我的文章：FLOYD算法
问题3：
一对关系是两个人名 不知道有几对关系的情况 用字符串读取全部人名 然后按空格分割 一次提取两个人名 用字符串流stringstream实现
参考我的文章用getline和stringstream读取一个字符串并按照空格分割
问题4：
输入的是人名，但是数组下标是数字。所以我们用map映射，构建一个map<string,int>.把一个名字映射到一个数字。因为map不会有重复元素。所以每出现一个新名字就在map中创建一对pair加入。就用不一样的数字代表名字。
题解代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<set>
#include<sstream>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
int dis[55][55];//两点间距离
int fa[55];//并查集 模板
int finds(int a){
int aa=a;//保存一下查找的点 也就是路径的底部
if(a!=fa[a]){
fa[a]=finds(fa[a]);//找到了根节点
}
while(aa!=fa[a]){//向上更新整条路径
int temp=fa[aa];//先存储路径的下一个点
fa[aa]=fa[a];//路径压缩一个
aa=temp;//再压缩下一个点
}
return fa[a];
}
void unions(int x,int y){
int fx=finds(x);
int fy=finds(y);
if(fx!=fy){
fa[fx]=fy;
}
}
void init(){//初始化fa数组 dis数组 便于多次
for(int i=0;i<55;++i){
fa[i]=i;
for (int j=0;j<55;++j){
if(i==j){
dis[i][j]=0;//自己到自己距离为0
}else{
dis[i][j]=INF;
}
}
}
}
int main(){
int x,y;
int cas=0;//输出第几个网络
while(cin>>x>>y){
cin.get();//读取一个空格
if(!x&&!y){
break;
}
init();//初始化
string temp;
getline(cin,temp);
stringstream str(temp);
string word1,word2;
map<string,int>m;
int num=0;
while(str>>word1>>word2){
if(m.find(word1)==m.end()){
m.insert(make_pair(word1,num++));
}
if(m.find(word2)==m.end()){
m.insert(make_pair(word2,num++));
}
int a=m[word1];
int b=m[word2];
unions(a,b);//并查集
dis[a][b]=1;
dis[b][a]=1;
}
//判断是否连通
if(num<x){//点少于总点数 肯定不联通
printf("Network %d: DISCONNECTED\n", ++cas);
cout<<endl;
continue;
}
int sum=0;//用并查集看是否属于同一个集合
for(int i=0;i<x;++i){
if(sum>1){
break;
}
if(fa[i]==i){
sum++;
}
}
if(sum!=1){
printf("Network %d: DISCONNECTED\n", ++cas);
cout<<endl;
continue;
}
//floyd 计算最短路径
for(int k=0;k<x;++k){//中转点
for(int i=0;i<x;++i){//每一对邻接点
for(int j=0;j<x;++j){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
int maxdis=-INF;
for(int i=0;i<x;++i){//每一对邻接点
for(int j=0;j<x;++j){
maxdis=max(dis[i][j],maxdis);
}
}
printf("Network %d: %d\n", ++cas, maxdis);
cout<<endl;
}
return 0;
}
Code详细解释：
1. 全局变量与数据结构
dis数组：初始化为INF（无穷大），表示初始不可达；对角线dis[i][i]设为0（自己到自己距离为0）。fa数组：并查集的父节点数组，用于快速判断连通性。
2. 并查集操作
- 路径压缩：确保查找操作的时间复杂度接近O(1)。
- 合并操作：将两个节点所在的集合合并，用于后续连通性判断。
3. 初始化函数 init()
- 作用：每次测试用例开始前，重置并查集和距离矩阵。
4. 节点映射与边处理
- 使用
map<string, int>将节点名转换为连续的整数ID（如0, 1, 2,...）。 - 对于每对节点，设置
dis[a][b] = dis[b][a] = 1，表示直接相连。
5.连通性检测
- 条件1：
num < x：若实际节点数少于输入的x，说明输入数据不完整，网络不连通。 - 条件2：通过并查集统计根节点数量。若根节点数
sum != 1，说明存在多个连通分量。
6.Floyd算法
- 原理：三重循环遍历所有可能的中间节点
k，更新所有点对的最短路径。 - 正确性：确保所有路径的最小值被计算。
7.最大分离度计算
- 遍历所有点对，排除
i == j的情况，取最大值maxdis。