fork(4) download
copy 
  1.  
  2.  
  3. 			import java.io.*;
  4. 			import java.util.*;
  5. 			class Main
  6. 			{
  7. 				static int colour[];
  8. 				//static boolean[] visited;
  9. 				static ArrayList <Integer> [] graph;
  10. 				public static void main(String args[])
  11. 				throws IOException
  12. 				{
  13. 					BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  14. 					int T=Integer.parseInt(br.readLine());
  15. 					for(int t=1;t<=T;t++)
  16. 					{
  17. 						String in[]=br.readLine().split(" ");
  18. 						int n=Integer.parseInt(in[0]);
  19. 						int m=Integer.parseInt(in[1]);
  20. 						//declaring array of arraylist such that the ith index of
  21. 						// the array will have all its neighbours in a list
  22. 						graph=new ArrayList[n+2];
  23. 						colour=new int[n+2];
  24. 						//visited=new boolean[n+2];
  25. 						for(int i=0;i<n+2;i++)
  26. 							graph[i]=new ArrayList<Integer>();
  27. 						//now for m different interactions
  28. 						for(int i=0;i<m;i++)
  29. 						{
  30. 							in=br.readLine().split(" ");
  31. 							int a=Integer.parseInt(in[0]);
  32. 							int b=Integer.parseInt(in[1]);
  33. 							graph[a].add(b);
  34. 							graph[b].add(a);
  35.  
  36. 						}
  37. 						boolean check=bfs(1);
  38. 						//System.out.println(check);
  39. 						if(!check)
  40. 							System.out.println("Scenario #"+t+":\nSuspicious bugs found!");
  41. 						else
  42. 							System.out.println("Scenario #"+t+":\nNo suspicious bugs found!");
  43.  
  44. 						//for(int j=0;j<colour.length;j++)
  45. 							//System.out.println(j+" "+colour[j]);
  46. 					}
  47.  
  48. 				}
  49.  
  50. 				static boolean bfs(int rootnode)
  51. 				{
  52. 					Queue<Integer> queue = new LinkedList();
  53. 					queue.add(rootnode);
  54. 					//visited[rootnode]=true;
  55. 					colour[rootnode]=1;
  56. 					while(!queue.isEmpty())
  57. 					{
  58. 						int u=queue.remove();//removing rootnode at beginning
  59. 						int base_colour=colour[u];
  60. 						//for each v in adj list of u
  61. 						ArrayList<Integer> adj_list=graph[u];
  62. 						Iterator<Integer> it=adj_list.iterator();
  63. 						while(it.hasNext())
  64. 						{
  65. 							int node=it.next();//only if node is unvisited
  66.  
  67. 								if(colour[node]!=0 && colour[node]==base_colour)
  68. 									return false;//not bipartite
  69.  
  70. 								if(colour[node]==0)
  71. 								{
  72. 									colour[node]=base_colour*-1;
  73. 									queue.add(node);
  74. 									//visited[node]=true;
  75. 								}
  76.  
  77. 						}
  78.  
  79. 					}
  80. 					return true;
  81. 				}
  82. 			}
  83.  
  84.  
  85.  
Success #stdin #stdout 0.08s 381248KB
comments (?)
stdin
copy 
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
stdout
copy 
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
https://ideone.com/IKJO4U
language:
Java (HotSpot 12)
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!