java - 查找不交集的数量

我试图找出给定N集和m关系的不相交集的个数例如，给定一个关系“i j”，我必须合并包含这两个元素的集合。m和n可以大到100000。
我试过使用哈希集的arraylist。但无法有效实施这是我的密码：

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
import java.lang.Object;

class fire
{
public static void main(String[] args)throws Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n,m;
    int t=Integer.parseInt(br.readLine());
    String st[];
    while(t-->0)
    {
        st=br.readLine().split(" ");
        n=Integer.parseInt(st[0]);
        m=Integer.parseInt(st[1]);
        ArrayList<HashSet<Integer>> list = new ArrayList<HashSet<Integer>>(n+1);

        for(int i=0;i<n+1;i++)
        {
            list.add(i, new HashSet<Integer>());
            list.get(i).add(i);
        }

        int a,b;
        while(m-->0)
        {
            st=br.readLine().split(" ");
            a=Integer.parseInt(st[0]);
            b=Integer.parseInt(st[1]);
            if(list.get(a).contains(a))
            {
                    if(list.get(b).contains(b))
                    {
                        Iterator<Integer> it = list.get(b).iterator();
                        while(it.hasNext())
                        {
                            list.get(a).add(new Integer((int)it.next()));
                        }
                        list.get(b).clear();
                    }
                    else
                    {
                        for(int i=1;i<n+1;i++)
                            if(list.get(i).contains(b))
                            {
                                if(i!=a)
                                {
                                    Iterator<Integer> it = list.get(i).iterator();
                                    while(it.hasNext())
                                        list.get(a).add(new Integer((int)it.next()));
                                    list.get(i).clear();
                                }
                                break;
                            }
                    }
            }
            else
            {
                for(int i=1;i<n+1;i++)
                    if(list.get(i).contains(a))
                    {
                        if(list.get(b).contains(b))
                        {
                            Iterator<Integer> it = list.get(b).iterator();
                            while(it.hasNext())
                                list.get(a).add(new Integer((int)it.next()));
                            list.get(b).clear();
                        }
                        else
                        {
                            for(int j=1;j<n+1;j++)
                                if(list.get(j).contains(b))
                                {
                                    if(i!=j)
                                    {
                                        Iterator<Integer> it = list.get(j).iterator();
                                        while(it.hasNext())
                                            list.get(a).add(new Integer((int)it.next()));
                                        list.get(j).clear();
                                    }
                                    break;
                                }
                        }
                        break;
                    }
            }
        }
        int size=0,prod=1;
        int num=0;
        for(int i=1;i<n+1;i++)
        {
            num=list.get(i).size();
            if(num!=0)
            {
                prod*=num;
                size++;
            }
        }
        System.out.println(size+" "+prod);
    }
}
};

这是codechef的问题。解决方法是正确的，但我正在为这个问题争取时间限制。我应该改进这段代码，还是必须使用不同的数据结构任何想法都会非常感谢：）。谢谢您。

最佳答案

您应该使用disjoint set forest数据结构来解决此问题。很容易实现，效率极高。

关于java - 查找不交集的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15324430/