POJ1611 并查集
这个题目是并查集的相对交简单的题目。本人第一词一次提交就ac，鸡冻呀。
将所有的组学生都union到一起，最后找到0号学生所在组的人数输出就可以了。
package test;import java.util.Scanner;public class Main {static node[] stus = new node[30001];public static void main(String args[]) {Scanner cin = new Scanner(System.in);int n = cin.nextInt();int m = cin.nextInt();while (n != 0) {if (m == 0) {System.out.println(1);} else {init();// 初始化while (m > 0) {// 输入每一个组的人员idm--;int num = cin.nextInt();// 组里的人数int x = cin.nextInt();// 输入的第一个元素while (num != 1) {num--;union(x, cin.nextInt());// 本组中的每一个元素都跟x放在同一个组里}}// 查找0号学生所在组的人数int sick = stus[find(0)].childnum + 1;System.out.println(sick);}// 下一个casen = cin.nextInt();m = cin.nextInt();}}public static void init() {for (int i = 0; i < stus.length; i++) {stus[i] = new node();stus[i].childnum = 0;stus[i].parent = i;// 初始化每一个元素组成一个集合}}public static int find(int x) {// 查找元素x所在的集合，返回根节点if (stus[x].parent == x)return x;stus[x].parent = find(stus[x].parent);return stus[x].parent;}public static void union(int x, int y) {// 将两个结合合并int px = find(x);// x的父亲节点int py = find(y);// y的父亲节点if (px == py)// 如果x和y本来就是在同一个组里的，不用合并return;if (stus[px].childnum >= stus[py].childnum) {// 如果x的孩子多，则把y加到x上stus[py].parent = px;stus[px].childnum += stus[py].childnum + 1;} else {// 如果y的孩子多，则把x加到y上stus[px].parent = py;stus[py].childnum += stus[px].childnum + 1;}}// 初始化统计每个集合都只有1个人// 只要是跟X同一个集合的都连上去// 最后搜索0属于哪个集合，这个集合有多少人}class node {int parent;int childnum;}
ps:今天【2012-9-22】再看这段代码的时候，发现里面错了一点。
if (m == 0) {System.out.println(n);}
当m==0的时候，应该输出的是n的数量，而不仅仅是1。看来这道题的数据量也不是很大。
-—————————————————————————-魂歌——————————————————————————
2012-09-28：
今天看了一个百度的笔试题，是集合合并的问题。http://www.yjbys.com/qiuzhizhinan/show-52701.html的第五题。
可以先将字符串编码为数字，比如说aaa对应数字1，bbb对应数字2，以此类推，然后将集合作为数字的集合，按照并查集的思路进行合并，然后再将集合还原成为字符串的集合，根据并查集的结果进行组装就形成了合并之后的结果。
╰半夏微凉°
淩亂°似流年
小灰灰
左手的ㄟ右手
灰太狼
不念不忘少年蓝@
还没有评论，来说两句吧...