自学1-摩杜云开发者社区

Problem1 明明的随机数

## 题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（N <= 100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

## 输入格式

输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。

第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

## 输出格式

输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

## 样例输入

10

20 40 32 67 40 20 89 300 400 15

## 样例输出

8
15 20 32 40 67 89 300 400

## 题解

由题目可知，这是一道关于“排序”和“去重”的问题，我们首先要进行排序，因为排序后的数列如果有相同的数字那一定是连续的，可以由它后面的一个数字代替（即当出现相同数字时，后面整体数字前移一位）。

## AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() { 5 int n, sum = 0; 6 int a[110]; 7 cin >> n; 8 for(int i = 1; i <= n; i ++) 9 cin >> a[i]; 10 sort(a + 1, a + 1 + n); 11 for(int i = 1; i <= n; i ++) 12 if(a[i] != a[i + 1]) 13 sum ++; 14 cout << sum << endl; 15 for(int i = 1; i <= n; i ++) 16 if(a[i] != a[i + 1]) 17 cout << a[i] << " "; 18 return 0; 19 }

## 拓展

这道题可以通过使用STL做，代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 set<int> s; 5 6 int main() { 7 int n, num; 8 cin >> n; 9 for(int i = 0; i < n; i ++) { 10 cin >> num; 11  s.insert(num); 12  } 13 cout << s.size() << endl; 14 while(s.empty() == 0) { 15 cout << *s.begin() << " "; 16  s.erase(s.begin()); 17  } 18 return 0; 19 }

Problem2 村村通

## 题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

## 输入格式

输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目

注意：两个城市间可以有多条道路相通。

在输入数据的最后，为一行一个整数

$## 输出格式$

$对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。$

$## 样例输入$

$## 样例输出$

$## 题解$

$这道题考察的是并查集。$

$我们首先要处理每一条存在的边，把所有存在的边所连接的两个结点用并查集合并。$

$然后记录不同的代表元素个数，即可得知连通块数量。$

$## AC代码$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010; 5 int f[N]; 6 int n, m; 7 8 //初始化 9 void init() { 10 for(int i = 1; i <= n; i ++) 11 f[i] = i;//自己的父亲就是自己 12 } 13 14 //寻找祖先 15 int find(int x) { 16 if(f[x] == x) 17 return x; 18 return f[x] = find(f[x]); 19 } 20 21 int main() { 22 23 while(cin >> n >> m) { 24  init(); 25 while(m --) { 26 int a, b; 27 cin >> a >> b; 28 int x = find(a), y = find(b);//压缩路径 29 f[x] = y; 30  } 31 int ans = 0; 32 for(int i = 1; i <= n; i ++) 33 if(f[i] == i)//合并集合后，自己的父亲就是自己的，视作生成树 34 ans ++; 35 //ans个连通块可以看作ans个结点，那么ans个结点并入一个生成树需要ans-1条边 36 cout << ans - 1 << endl; 37  } 38 return 0; 39 }