0

我试图找到给定N个集合和M个关系的不相交集合的数量。例如，给定一个关系“ ij ”，我必须合并包含这两个元素的集合。M 和 N 可以大到 100000。

我尝试使用ArrayList of Hashsets。但无法有效实施。这是我的代码：

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 的一个问题。解决方案是正确的，但我正在为这个问题获得 TimeLimitExceeded。我应该努力改进此代码还是必须使用不同的数据结构？任何想法都会非常感激:)。谢谢你。

4

1 回答 1

1

你应该使用不相交的集合森林数据结构来解决这个问题。非常容易实施并且非常高效。

于 2013-03-10T16:17:19.897 回答