import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input;
StringBuffer sb = new StringBuffer("");
int testcases = Integer.parseInt(br.readLine());
br.readLine();
for (int i = 0; i < testcases; i++)
{
if(i>0)
sb.append("\n");
int no_of_computers=Integer.parseInt(br.readLine());
UnionFindDisjoint.initSet(no_of_computers);
int N1=0;
int N2=0;
while((input=br.readLine())!=null)
{
if(input.trim().equals(""))
break;
String s[]=input.split(" ");
switch (s[0])
{
case "c":
{
UnionFindDisjoint.union(Integer.parseInt(s[1])-1,Integer.parseInt(s[2])-1);
break;
}
case "q":
{
if(UnionFindDisjoint.isSameSet(Integer.parseInt(s[1])-1,Integer.parseInt(s[2])-1))
{
N1++;
}
else
N2++;
break;
}
}
}
sb.append(N1+","+N2+"\n");
}
System.out.print(sb);
}
}
class UnionFindDisjoint
{
static int pset[];
public static void initSet(int size)
{
pset=new int[size];
for (int i = 0; i < size; i++)
{
pset[i]=i;
}
}
public static int findSet(int i)
{
return (pset[i] == i) ? i : (pset[i] = findSet(pset[i]));
}
public static void union(int i,int j)
{
pset[findSet(i)] = findSet(j);
}
public static boolean isSameSet(int i,int j)
{
return findSet(i) == findSet(j);
}
}
UVA Problem ID 793 ( Network Connections)
Tags:
793
java
union-find
UVa

0 comments: