2011年ACM-ICPC协会程序设计大赛解题报告（part1）,PSJay 09计科,Problem1 : ZOJ,Problem1 : ZOJ,Description 读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。,Problem1 : ZOJ,Input 题目包含多组用例,每组用例占一行，包含ZOJ三个字符，当输入“E”时表示输入结束。1=length=100。 Output 对于每组输入,请输出一行，表示按照要求处理后的字符串。 具体可见样例。,Problem1 : ZOJ,Problem1 : ZOJ,Analysis 要将字符串按照 ZOJ 的顺序输出，只需要记录字符 Z、O、J 各自在字符串中出现的次数即可。,Problem1 : ZOJ,Solution 输入字符串； 分析字符串，分别记录字符 Z , O , J 出现的次数； 输出结果。,Problem1 : ZOJ,Beginners Guide 解题格式； Input 和 Output 的格式； 不管通过何种方式实现，只需输出正确答案。,Problem2 : 畅通工程,Problem2 : 畅通工程,Description 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？,Problem2 : 畅通工程,Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目( N 1000 ) 和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。,Problem2 : 畅通工程,Output 对每个测试用例，在1行里输出最少还需要建设的道路数目。,Problem2 : 畅通工程,Problem2 : 畅通工程,Analysis,1,2,3,4,Case 1:,Problem2 : 畅通工程,Analysis,1,2,3,Case 2:,Problem2 : 畅通工程,Analysis,1,2,3,4,5,Case 3:,Problem2 : 畅通工程,Key Point,找出 n 个互不相交的城镇集合，结果就为 n 1。,Problem2 : 畅通工程,Preparation Knowledge,表示集合的三种方式（数据结构）： 数组， 树， 图。,Problem2 : 畅通工程,Preparation Knowledge,Problem2 : 畅通工程,Solution 假设每个城市都是不相交的；（每个元素都是树根） 随着道路的连接，将连通的城市合并到同一个集合； （集合中的元素拥有同样的树根） 统计出一共有多少个集合，输出结果。,Problem2 : 畅通工程,Examples,1,2,3,4,5,Problem2 : 畅通工程,Examples,