POJ1611 并查集

╰半夏微凉° 2022-09-30 03:46 17阅读 0赞

这个题目是并查集的相对交简单的题目。本人第一词一次提交就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) {// 输入每一个组的人员id
    					m--;
    					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);
    			}
    			// 下一个case
    			n = 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，以此类推，然后将集合作为数字的集合，按照并查集的思路进行合并，然后再将集合还原成为字符串的集合，根据并查集的结果进行组装就形成了合并之后的结果。