fork download
copy 
  1. import java.util.Arrays;
  2. import java.util.PriorityQueue;
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  * Created by rajanW(683281) on 03-Apr-15.
  7.  * at 1:12 PM
  8.  * Very easy Bipartite test
  9.  */
  10. class ClawDecomposition_11396 {
  11.  
  12.     static int n;
  13.     static int g[][];
  14.     static int color[];
  15.  
  16.     static boolean bfs(int u){
  17.         color[u]=1;
  18.         PriorityQueue<Integer> q = new PriorityQueue<Integer>();
  19.         q.add(u);
  20.         while(!q.isEmpty()){
  21.             int i = q.poll();
  22.             for(int j=0;j<n;j++){
  23.                 if(g[i][j]==1){
  24.                     if(color[j]==-1){color[j]=1-color[i];q.add(j);}	//if not visited yet then color different
  25.                     else if(color[j]==color[i]){return false;}	// if same color then game over
  26.                 }
  27.             }
  28.         }
  29.         return true;
  30.     }
  31.  
  32.     static boolean bptest(){
  33.         for(int i=0;i<n;i++){
  34.             if(color[i]==-1) {	// check for all connected components
  35.                 if (!bfs(i)) {
  36.                     return false;
  37.                 }
  38.             }
  39.         }
  40.         return true;
  41.     }
  42.  
  43.     public static void main(String args[]) throws Exception{
  44.         Scanner sc = new Scanner(System.in);
  45.         int x,y,i,j,ans;
  46.         while(true){
  47.             n = sc.nextInt();
  48.             if(n==0){break;}
  49.             g = new int[n][n];
  50.             color = new int[n];
  51.             Arrays.fill(color,-1);
  52.             while(true){
  53.                 x = sc.nextInt(); y = sc.nextInt();
  54.                 if(x==y&&x==0){break;}
  55.                 g[x-1][y-1]=g[y-1][x-1]=1;
  56.             }//graph is complete
  57.             if(bptest()){
  58.                 System.out.println("YES");
  59.             }
  60.             else{System.out.println("NO");}
  61.         }
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.1s 380608KB
comments (?)
stdin
copy 
4

1 2

1 3

1 4

2 3

2 4

3 4

0 0

6

1 2

1 3

1 6

2 3

2 5

3 4

4 5

4 6

5 6

0 0

0
stdout
copy 
NO
NO
https://ideone.com/1mIRcI
language:
Java (12.0.1)
created:
9 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!