我试图找到给定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。我应该努力改进此代码还是必须使用不同的数据结构？任何想法都会非常感激:)。谢谢你。