[开发测试]谁是你的潜在朋友（哈希表）and还是畅通工程（最小生成树）

题目 1721: 谁是你的潜在朋友

原题地址
题目描述

“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会
并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。
首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。

输入

每个案例第一行两个整数N,M，2 <= N ，M<= 200。
接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，
表示读者i-1最喜欢的图书的编号P(1<=P<=M)

输出

每个案例包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）

样例输入

4 5
2
3
2
1

样例输出

1
BeiJu
1
BeiJu

注意细节

题目说了是每个案例，说明是多组输入

暴力解法

时间复杂度：O(n²)

#include<iostream>
#include<algorithm>
using namespace std;

//book[]用来保存数的编号，数组下标记录读者序号
int book[100000];

int main()
{
	int n, m;
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++) {
			cin >> book[i];
		}
		int count;
		for (int i = 1; i <= n; i++) {//遍历所有读者
			count = 0;//记录朋友个数
			for (int j = 1; j <= n; j++) {//遍历所有读者
			//读者i与读者j的书籍编号相同，且i和j不是同一个人
			//则朋友数加1
				if (book[i] == book[j] && i != j) {
					count++;
				}
			}
			//不为0则输出朋友数
			if (count) {
				cout << count << endl;
			}
			//没有朋友则输出"BeiJu"
			else {
				cout << "BeiJu" << endl;
			}
		}
	}
	
	return 0;

}

Hash表

时间复杂度：O(n)

#include<iostream>
#include<algorithm>
using namespace std;

int book[100000];
//下标是读者的编号，对应的值是读者喜欢的书的编号

int main()
{
	int n, m;
	while (cin >> n >> m) {
		int Hash[210] = { 0 };//下标是书的编号，对应的值是喜欢这本书的人数
		for (int i = 1; i <= n; i++) {
			cin >> book[i];
			Hash[book[i]]++;
		}
		for (int i = 1; i <= n; i++) {
			if (Hash[book[i]] == 1) {
				cout << "BeiJu" << endl;
			}
			else {
				cout << Hash[book[i]] - 1 << endl;
			}
		}
	}

	return 0;

}

题目 1729: 还是畅通工程

题目描述

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100
)；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

输出

对每个测试用例，在1行里输出最小的公路总长度。

样例输入

8
1 2 42
1 3 68
1 4 35
1 5 1
1 6 70
1 7 25
1 8 79
2 3 59
2 4 63
2 5 65
2 6 6
2 7 46
2 8 82
3 4 28
3 5 62
3 6 92
3 7 96
3 8 43
4 5 28
4 6 37
4 7 92
4 8 5
5 6 3
5 7 54
5 8 93
6 7 83
6 8 22
7 8 17
0

样例输出

82

细节注意

1. 这是一道最小生成树的题目，套模板即可
2. 我写出来后老是报错：输出超限，看了别人的解释，一改就通过了，奇奇怪怪的知识又增加了
3. 将scanf或gets的内容放到while里面，或者还可以在while的括号里面加上！=EOF
4. 传送门

Kruskal算法

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 100 + 10;
const int maxn2 = maxn * (maxn - 1) / 2;

struct edge {
	int l, r, w;
}a[maxn2];

int node[maxn];

bool cmp(edge a, edge b) { return a.w < b.w; }

int find(int x) { return x == node[x] ? x : find(node[x]); }

int main()
{
	int n, m;
	//将cin>>n写在while()里
	while (cin >> n) {
		if (n == 0) {
			continue;
		}
		m = n * (n - 1) / 2;
		for (int i = 1; i <= m; i++) {
			cin >> a[i].l >> a[i].r >> a[i].w;
		}
		sort(a + 1, a + m + 1, cmp);

		for (int i = 1; i <= n; i++) {
			node[i] = i;
		}

		int ans = 0, sum = 0;
		for (int i = 1; i <= m && ans < n - 1; i++) {
			int xx = find(a[i].l);
			int yy = find(a[i].r);
			if (xx == yy) {
				continue;
			}
			else {
				ans++;
				node[yy] = xx;
				sum += a[i].w;
			}
		}
		printf("%d\n", sum);
	}
	return 0;
}