fork download
copy 
  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3.  
  4. public class Main
  5. {
  6.     static ArrayList<Integer>g[]=new ArrayList[20005];
  7.     static boolean vis[]=new boolean[20005];
  8.     static int xx,yy;
  9.  
  10.     static void dfs(int source, boolean p)
  11.     {
  12.         if(vis[source]==true)
  13.         return;
  14.         vis[source]=true;
  15.         if(p)
  16.         xx++;
  17.         else
  18.         yy++;
  19.         int sz=g[source].size();
  20.         for(int i=0;i<sz;i++)
  21.         dfs(g[source].get(i),!p);
  22.         return;
  23.     }
  24.  
  25.     public static void main(String[] args)
  26.     {
  27.         for (int i=0; i<20005; i++)
  28.             g[i] = new ArrayList<>();
  29.  
  30.         Scanner s=new Scanner(System.in);
  31.         int t,n,a,b;
  32.         t=s.nextInt();
  33.         for(int i=1;i<=t;i++)
  34.         {
  35.             for(int j=0;j<20005;j++)
  36.                 g[j].clear();
  37.  
  38.             for(int j=0;j<20005;j++)
  39.                 vis[j]=false;
  40.  
  41.             n=s.nextInt();
  42.  
  43.             for(int j=1;j<=n;j++)
  44.             {
  45.                 a=s.nextInt();
  46.                 b=s.nextInt();
  47.                 g[a].add(b);
  48.                 g[b].add(a);
  49.             }
  50.  
  51.             int ans=0;
  52.             for(int j=1;j<20005;j++)
  53.             if(vis[j]==false && !g[j].isEmpty())
  54.             {
  55.                     xx=yy=0;
  56.                     dfs(j,true);
  57.                     ans+=Math.max(xx,yy);
  58.             }
  59.             System.out.println("Case "+i+": "+ans);
  60.             System.gc();
  61.         }
  62.         System.gc();
  63.         s.close();
  64.     }
  65. }
Success #stdin #stdout 0.14s 3359744KB
comments (?)
stdin
copy 
1
6
1 2
3 4
5 6
2 7
2 8
3 9
stdout
copy 
Case 1: 6
https://ideone.com/so3oF3
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!