第十篇博客——图论
并查集
图论中我认为最好玩的算法就是并查集了，基本上常用的并查集算法如下：
初始化
void init(int n){ for(int i=0;i<=n;i++){ fa[i]=i;//每个节点的父亲都是自己 he[i]=0;//每个节点的高度是0 } }查找并压缩路径（这样可以更好地获得菊花图）
int find(int x){ if(x!=fa[x]) fa[x]=find(fa[x]); //路径压缩，一般的方法只是返回fa[x]，这里还压缩了路径，让树不至于退化成链表 else return fa[x]; }合并
//合并要保证矮树作为高树的子树 void union(int x,int y){ x=find(x); y=find(y); if(x!=y){ if(he[x]<he[y]) fa[x]=fa[y]; else if(he[x]>he[y]) fa[y]=fa[x]; else{ fa[y]=x; he[x]++;//新建一个节点 } } return; }
练习：链接：https://www.nowcoder.com/questionTerminal/4878e6c6a24e443aac5211d194cf3913
来源：牛客网
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。输出描述:
对每个测试用例，在1行里输出最少还需要建设的道路数目。
//将每个元素看为一个集合，然后通过并查集合并集合，然后再将余下的集合连接起来即可
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;//城镇和道路数量
while(cin>>n>>m){
int t=n;//现在的所有的城市都是不相通的
vector<int> v(n+1,-1);
while(m--){//输入路径
int x,y;
cin>>x>>y;//这条路连着的两个城市：x和y
int a=x,b=y;
while(v[a]!=-1)
a=v[a];//找代表元素
while(v[b]!=-1)
b=v[b];
if(a==b)//a和b是一个节点
continue;
else//a和b分别是不同的根节点
v[b]=x,t-=1;//合并集合，让b的根部等于原本a（因为现在的a已经更改了）
//同时需要建造的道路--
}
v.clear();
cout<<t-1<<endl;
}
} 除此之外还有一种计算的方法，那就是开始的时候设置ans=-1，在设置后查找有多少个集合，集合数量加上ans就是需要新建的道路数量。实际上，至少有一个集合，那么ans最小等于0.
判断集合个数的代码如下：
for(int i=0;i<n;i++){
if(find(i)==i)
ans;
} 最小生成树
关于最小生成树有Kruskal算法和Prim算法，其中Kruskal算法比较简单，需要联系并查集.
练习：
链接：https://www.nowcoder.com/questionTerminal/d6bd75dbb36e410995f8673a6a2e2229
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。输出描述:
对每个测试用例，在1行里输出最小的公路总长度。
//
// main.cpp
// test0129
//
// Created by 章笙 on 2021/1/29.
//
//要求总路线最短，那一定就是克鲁斯卡尔算法求最小生成树
#include <iostream>
#include <cstdio>
#include<algorithm>
using namespace std;
const int maxn=100;
struct edge{
int from;
int to;
int length;
bool operator< (const edge& e)const{
return length<e.length;
}
};
//用一维数组代表图（实际上存储的是边）
edge e[maxn*maxn];
//下面和模版中的一样
int father[maxn];
int height[maxn];
void initial(int n){
for(int i=0;i<=n;i++){
father[i]=i;
height[i]=0;
}
}
int find(int x){
if(father[x]!=x)
father[x]=find(father[x]);
return father[x];
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
if(height[x]<height[y])
father[x]=y;
else if(height[x]>height[y])
father[y]=x;
//找到了盲点：这里不能只用if，能用else就用else
else{
father[y]=x;
height[x]++;
}
}
return;
}
int Kruskal(int n,int edgenum){
initial(n);
sort(e, e+edgenum);//按照升序排列（有重载小于号）
int sum=0;
for(int i=0;i<edgenum;i++){
edge cur=e[i];
if(find(cur.from)!=find(cur.to)){
Union(cur.from,cur.to);
sum+=cur.length;
}
}
return sum;
}
int main(){
int n;
while(cin>>n){
if(n==0){
break;
}
int edgenum=n*(n-1)/2;//高斯求和
for(int i=0;i<edgenum;i++){
cin>>e[i].from>>e[i].to>>e[i].length;
}
cout<<Kruskal(n,edgenum)<<endl;
}
return 0;
}
练习：
链接：https://www.nowcoder.com/questionTerminal/41b14b4cd0e5448fb071743e504063cf
来源：牛客网
In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.
输入描述:
The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.
输出描述:
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.
这道题本质上和上一题的思路是一样的，但是由于本题中的点是具体的x和y坐标所以需要引入一个新的结构体：点（Point）
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>//为了算距离
using namespace std;
int n;
const int maxn=101;
float res;
struct Point{
float x,y;
};
struct G{
int from;
int to;
float weight;
inline bool operator <(const G &g)const{
return weight<g.weight;
}
};
vector<G> graph;
vector<Point> vec;
int father[maxn];
int height[maxn];
void init(int n){
for(int i=0;i<=n;i++){
father[i]=i;
height[i]=0;
}graph.clear();
vec.clear();
res=0;
}
float getdis(Point x,Point y){
return pow((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y),0.5);
}
int find(int x){
if(x!=father[x]){
father[x]=find(father[x]);
}
return father[x];
}
void Union(int x,int y,float weight){
x=find(x);
y=find(y);
if(x!=y){
res+=weight;
if(height[x]>height[y]){
father[y]=x;
}else if(height[x]<height[y]){
father[x]=y;
}else{
father[x]=y;
height[y]++;
}
}
}
//在这里将res的增加放在Union里了
int main(){
while(cin>>n){//有n个点
init(n);
Point p;
G g;
for(int i=0;i<n;i++){
cin>>p.x>>p.y;
vec.push_back(p);
}
for(int i=0;i<vec.size()-1;i++){
for(int j=i+1;j<vec.size();j++)//全排列
{
g.from=i;
g.to=j;
g.weight=getdis(vec[i],vec[j]);
graph.push_back(g);
}
}
sort(graph.begin(),graph.end());
//下面的部分将kruskal融入主函数
for(int i=0;i<graph.size();i++){
Union(graph[i].from,graph[i].to,graph[i].weight);
}
printf("%.2f\n",res);
}
return 0;
} 本题也可以和上题一样，将Kruskal列出来，代码如下：
float Kruskal(int n){
sort(graph.begin(),graph.end());
for(int i=0;i<graph.size();i++){
Union(graph[i].from,graph[i].to,graph[i].weight);
}
return res;
}
int main(){
while(cin>>n){
init(n);
Point p;
G g;
for(int i=0;i<n;i++){
cin>>p.x>>p.y;
vec.push_back(p);
}
for(int i=0;i<vec.size()-1;i++){
for(int j=i+1;j<vec.size();j++)//全排列
{
g.from=i;
g.to=j;
g.weight=getdis(vec[i],vec[j]);
graph.push_back(g);
}
}
printf("%.2f\n",Kruskal(n));
}
return 0;
} 实际上第一个练习的代码不是很简洁，因为Union本来就是在find(x)!=find(y)的时候才会将两个节点联合，所以在Kruskal函数中没必要判断。
京公网安备 11010502036488号