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: