0

与えられたNセットとM関係の互いに素なセットの数を見つけようとしています。たとえば、関係「ij」が与えられた場合、これら2つの要素を含むセットをマージする必要があります。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の問題です。解決策は正しいですが、この問題に対してTimeLimitExceededを取得しています。このコードの改善に取り組む必要がありますか、それとも別のデータ構造を使用する必要がありますか？どんなアイデアでも本当にありがたいです:)。ありがとうございました。

4

1 に答える 1

1

この問題には、互いに素なセットフォレストデータ構造を使用する必要があります。実装が非常に簡単で、非常に効率的です。

于 2013-03-10T16:17:19.897 に答える