Thursday, 20 February 2014

UVA Problem ID 793 ( Network Connections)

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);
 }
}

Previous Post
Next Post

0 comments:

Advertisement