心双2024数据结构1050-1051&1055-1058题解-xiwwwix's blog

并查集&最小生成树的题目。课内不考并查集，教的最小生成树算法（Prim & Kruskal）应该都是简化版的，可以通过以下两篇博客简单了解并查集是什么，以及在Kruskal算法中的应用：
【算法与数据结构】—— 并查集
 kruskal算法透彻理解（含并查集及最小生成树的解释）

非常建议把并查集+最小生成树的模板背下来，代码量很小而且时间复杂度很低，即使对原理一知半解也可以用于速通机考（？）

1050. 朋友圈

每一行输入都是：先给出第i个俱乐部人数m，然后是第1~m个学生的编号

我们可以把第1个学生当成“组长”，只需要给并查集加上“组长”和每个其他组员的连边即可，这样就能形成每个以组长为核心的连通块（root相同的人），效果和把俱乐部内所有人两两配对加边是一样的

#include <bits/stdc++.h>
using namespace std;

int root[30005] = {0};
int cnt[30005] = {0};

int Findroot(int x) {
	if (x == root[x]) {
		return x;
	}
	root[x] = Findroot(root[x]);
	return root[x];
}

int Query(int x,int y) {
	return Findroot(x) == Findroot(y);
}

void Merge(int x,int y) {
	int rootx = Findroot(x);
	int rooty = Findroot(y);
	root[rootx] = rooty;
}

int main () {
	int n,m,f,p,k;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		root[i] = i;
	}
	while(m--) {
		cin >> k;
		cin >> f;
		for (int i = 1;i < k;i++) {
			cin >> p;
			Merge(f,p);
		}
	}
	
	for (int i = 1;i <= n;i++) {
		int r = Findroot(i);
		cnt[r]++;
	}
	
	int ans = 0;
	for (int i = 1;i <= n;i++) {
		ans = max(ans,cnt[i]);
	}
	
	cout << ans << endl;
	
	return 0;
}

1051. Virtual Friends

输入格式:
第一行输入一个整数，表示测试用例的数量。
每个测试用例的第一行包含一个整数F，表示形成的友谊数量（F≤100,000）。

接下来的F行，每行包含两个名字，表示刚刚成为朋友的两个人，名字之间用空格分隔。名字是一个由 1 到 20 个字母（大小写均可）组成的字符串。

输出格式:
每当形成一段友谊时，输出一行，包含一个整数，表示刚刚成为朋友的两个人的社交网络的总人数。

思路：使用并查集数据结构维护每个人的社交网络。
对于每对新得到的朋友关系，查找他们所在的集合，如果不在同一个集合，则合并这两个集合，并更新输出集合的大小（可以用cnt[i]表示根为i的连通块的大小）。

更新的核心代码：

if (!Query(id1,id2)) {
    int cnt1 = cnt[rootx];
    int cnt2 = cnt[rooty];
    cnt[rootx] += cnt2;
    cnt[rooty] += cnt1;
    Merge(id1,id2);
}

完整代码：

#include <bits/stdc++.h>
using namespace std;

int root[200005];
int cnt[200005] = {0};

int Findroot(int x) {
	if (x == root[x]) {
		return x;
	}
	root[x] = Findroot(root[x]);
	return root[x];
}

void Merge(int x,int y) {
	int rootx = Findroot(x);
	int rooty = Findroot(y);
	root[rootx] = rooty;
}

bool Query(int x,int y) {
	return Findroot(x) == Findroot(y);
}

void solve() {
	int n;
	map<string,int> id;
	cin >> n;
	string p1,p2;
	int c = 1;
	
	for (int i = 1;i <= 2*n;i++) {
		root[i] = i;
		cnt[i] = 1;
	}
	
	while (n--) {
		cin >> p1 >> p2;
		int id1,id2;
		if (!id[p1]) {
			id[p1] = c;
			c++;
		} 
		
		if (!id[p2]) {
			id[p2] = c;
			c++;
		}
		
		id1 = id[p1];
		id2 = id[p2];
		
		int rootx = Findroot(id1);
		int rooty = Findroot(id2);
		
		if (!Query(id1,id2)) {
			int cnt1 = cnt[rootx];
			int cnt2 = cnt[rooty];
			cnt[rootx] += cnt2;
			cnt[rooty] += cnt1;
			Merge(id1,id2);
		}
		cout << cnt[Findroot(id1)] << endl;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

接下来的1055-1058是最小生成树

1055. 公路村村通

基本上是模板题，只需要注意两个细节：

某两个城镇之间修建道路的方案可能不止一个，这个问题不大，反正Kruskal的思想是把所有边排序，权值越小的边越靠前被加进答案

输入数据可能不是连通图，只需要用并查集判断（i == root[i]）的个数就可以，等效思想是“只统计根的数量”

#include <bits/stdc++.h>
using namespace std;

int root[3005];

bool cmp(const vector<int>& a, const vector<int>& b) {
	return a[2] < b[2];
}

int Findroot(int x) {
	if (x != root[x]) {
		root[x] = Findroot(root[x]);
	}
	return root[x];
}

void Merge(int x,int y) {
	int rootx = Findroot(x);
	int rooty = Findroot(y);
	root[rootx] = rooty;
}

bool Query(int x,int y) {
	return Findroot(x) == Findroot(y);
}

vector<vector<int>> edges;
map<int,int> cc;

int main() {
	int n,m;
	int ans = 0;
	cin >> n >> m;
	int u,v,cost;
	
	for (int i = 1;i <= n; i++) {
		root[i] = i;
	}
	
	for(int i = 0;i < m;i++) {
		cin >> u >> v >> cost;
		vector<int> temp;
		edges.push_back({u,v,cost});
	}
	sort(edges.begin(),edges.end(),cmp);
	for(int i = 0;i < edges.size();i++) {
		u = edges[i][0];
		v = edges[i][1];
		cost = edges[i][2];
		if (!Query(u,v)) {
			ans += cost;
			Merge(u,v);
		}
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (Findroot(i) == i) {
			cnt++;
		}
	}
	
	if (cnt != 1) {
		cout << "-1" << endl;
	}else {
		cout << ans << endl;
	}
	
	return 0;
}

1056. Hub Connection plan

和上一题几乎一模一样


#include <bits/stdc++.h>
using namespace std;

int root[3005];

bool cmp(const vector<int>& a, const vector<int>& b) {
	return a[2] < b[2];
}

int Findroot(int x) {
	if (x != root[x]) {
		root[x] = Findroot(root[x]);
	}
	return root[x];
}

void Merge(int x,int y) {
	int rootx = Findroot(x);
	int rooty = Findroot(y);
	root[rootx] = rooty;
}

bool Query(int x,int y) {
	return Findroot(x) == Findroot(y);
}

vector<vector<int>> edges;
map<int,int> cc;

int main() {
	int n,m;
	int ans = 0;
	cin >> n >> m;
	int u,v,cost;
	
	for (int i = 1;i <= n; i++) {
		root[i] = i;
	}
	
	for(int i = 0;i < m;i++) {
		cin >> u >> v >> cost;
		vector<int> temp;
		temp.push_back(u);
		temp.push_back(v);
		temp.push_back(cost);
		edges.push_back(temp);
	}
	sort(edges.begin(),edges.end(),cmp);
	for(int i = 0;i < edges.size();i++) {
		u = edges[i][0];
		v = edges[i][1];
		cost = edges[i][2];
		if (!Query(u,v)) {
			ans += cost;
			Merge(u,v);
		}
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (Findroot(i) == i) {
			cnt++;
		}
	}
	
	if (cnt != 1) {
		cout << "-1" << endl;
	}else {
		cout << ans << endl;
	}
	
	return 0;
}

1057. Building Roads

题意：
Farmer John 有 N 个农场，每个农场的位置用平面坐标系中的点表示。已经有 M 条道路连接了一些农场。现在需要修建一些额外的道路，使得所有农场都连通（即从任意一个农场可以通过道路到达其他任意农场）。目标是计算需要修建的道路的最小总长度。

只需要计算所有农场之间的距离，生成所有可能的边，边权值等于距离，然后再添加已经存在的道路，这些道路权重设为 0，然后正常套最小生成树模板就可以了。

#include <bits/stdc++.h>
using namespace std;

vector<tuple<int, int, double>> edges; // 存储所有边，格式为 (u, v, weight)
int pos[1001][2] = {0x7f}; // 存储每个农场的坐标
int root[1005]; // 并查集的根节点数组

// 比较函数，用于按边的权重排序
bool cmp(const tuple<int, int, double>& a, const tuple<int, int, double>& b) {
    return get<2>(a) < get<2>(b);
}

// 查找节点的根节点，带路径压缩
int Findroot(int x) {
    if (x != root[x]) {
        root[x] = Findroot(root[x]);
    }
    return root[x];
}

// 合并两个集合
void Merge(int x, int y) {
    int rootx = Findroot(x);
    int rooty = Findroot(y);
    root[rootx] = rooty;
}

// 查询两个节点是否在同一个集合中
bool Query(int x, int y) {
    return Findroot(x) == Findroot(y);
}

// 计算两个农场之间的欧几里得距离
double distance(int xx1, int xx2, int yy1, int yy2) {
    return sqrtl(pow(xx1 - xx2, 2) + pow(yy1 - yy2, 2));
}

int main() {
    int n, m, x, y, u, v;

    cin >> n >> m; // 输入农场数量和已存在道路数量

    // 输入每个农场的坐标
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        pos[i][0] = x;
        pos[i][1] = y;
    }

    // 初始化并查集，每个节点的根节点为自己
    for (int i = 1; i <= n; i++) {
        root[i] = i;
    }

    // 输入已存在的道路，并将其权重设为 0
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        edges.push_back(make_tuple(u, v, 0));
    }

    // 计算所有农场之间的距离，生成所有可能的边
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue; // 避免自环
            double dis = distance(pos[i][0], pos[j][0], pos[i][1], pos[j][1]);
            edges.push_back(make_tuple(i, j, dis));
        }
    }

    double ans = 0; // 存储最小生成树的总长度
    sort(edges.begin(), edges.end(), cmp); // 按边的权重排序

    // Kruskal 算法：遍历所有边，构建最小生成树
    for (int i = 0; i < edges.size(); i++) {
        u = get<0>(edges[i]);
        v = get<1>(edges[i]);
        double cost = get<2>(edges[i]);

        // 如果两个节点不在同一个集合中，则合并它们，并将边的权重加入总长度
        if (!Query(u, v)) {
            ans += cost;
            Merge(u, v);
        }
    }

    // 输出结果，保留两位小数
    printf("%.2f", ans);

    return 0;
}

1058. 组网计划

要求次小生成树，挺难搞，不明白为什么这题标的是medium（详见(次小生成树)[https://oi-wiki.org/graph/mst/#%E6%AC%A1%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91]）

//耗时1.5h，泪目TAT
//这题标medium，尊嘟假嘟？

#include <bits/stdc++.h>
using namespace std;

int root[105]; // 并查集的根节点数组

// 计算曼哈顿距离
int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// 查找节点的根节点，带路径压缩
int Findroot(int x) {
    if (x != root[x]) {
        root[x] = Findroot(root[x]);
    }
    return root[x];
}

// 合并两个集合
void Merge(int x, int y) {
    int rootx = Findroot(x);
    int rooty = Findroot(y);
    if (rootx != rooty) {
        root[rooty] = rootx; // 将 y 的根节点指向 x 的根节点
    }
}

int main() {
    int n;
    while (cin >> n) { // 多组输入
        int pos[105][2]; // 存储每个点的坐标
        vector<vector<int>> edges; // 存储所有边，格式为 {权重, 点1, 点2}

        // 输入每个点的坐标
        for (int i = 1; i <= n; i++) {
            cin >> pos[i][0] >> pos[i][1];
        }

        // 计算所有点对之间的距离，并生成边
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int dis = distance(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);
                edges.push_back({dis, i, j});
            }
        }

        // 按边的权重从小到大排序
        sort(edges.begin(), edges.end());

        // 初始化并查集，每个节点的根节点为自己
        for (int i = 1; i <= n; i++) {
            root[i] = i;
        }

        int ans = 0; // 存储最小生成树的总长度
        bool flag = false; // 标记是否存在多种 MST 方案

        // Kruskal 算法：遍历所有边
        for (int i = 0; i < edges.size();) {
            int j = i;
            vector<vector<int>> sedges; // 存储当前相同权重的边

            // 找到所有权重相同的边
            while (j < edges.size() && edges[j][0] == edges[i][0]) {
                sedges.push_back(edges[j]);
                ++j;
            }

            vector<vector<int>> cedges; // 存储可以合并的边
            for (auto& edge : sedges) {
                int w = edge[0];
                int u = edge[1];
                int v = edge[2];
                int ru = Findroot(u);
                int rv = Findroot(v);

                // 如果两个节点不在同一个集合中，则记录这条边
                if (ru != rv) {
                    cedges.push_back({w, u, v});
                }
            }

            // 检查是否存在多种 MST 方案
            set<pair<int, int>> cc; // 存储可以合并的集合对
            for (auto& edge : cedges) {
                int u = edge[1];
                int v = edge[2];
                int ru = Findroot(u);
                int rv = Findroot(v);
                if (ru > rv) swap(ru, rv); // 确保集合对有序
                pair<int, int> temp = make_pair(ru, rv);
                if (cc.count(temp)) {
                    flag = true; // 如果集合对已存在，则存在多种 MST 方案
                } else {
                    cc.insert(temp);
                }
            }

            // 合并可以合并的边，并累加权重
            for (auto& edge : cedges) {
                int w = edge[0];
                int u = edge[1];
                int v = edge[2];
                int ru = Findroot(u);
                int rv = Findroot(v);
                if (ru != rv) {
                    Merge(u, v);
                    ans += w;
                }
            }

            i = j; // 跳过已处理的相同权重的边
        }

        // 输出结果
        cout << ans << endl; // 输出最小生成树的总长度
        cout << (flag ? "Yes" : "No") << endl; // 输出是否存在多种 MST 方案
    }

    return 0;
}