fork(3) download
copy 
  1.  
  2.  
  3.  
  4. 			import java.io.*;
  5. 			import java.util.*;
  6. 			class BUGLIFE
  7. 			{
  8. 				static int colour[];
  9. 				static boolean[] visited;
  10. 				static ArrayList <Integer> [] graph;
  11. 				public static void main(String args[])
  12. 				throws IOException
  13. 				{
  14. 					BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  15. 					int T=Integer.parseInt(br.readLine());
  16. 					for(int t=1;t<=T;t++)
  17. 					{
  18. 						String in[]=br.readLine().split(" ");
  19. 						int n=Integer.parseInt(in[0]);
  20. 						int m=Integer.parseInt(in[1]);
  21. 						//declaring array of arraylist such that the ith index of
  22. 						// the array will have all its neighbours in a list
  23. 						graph=new ArrayList[n+2];
  24. 						colour=new int[n+2];
  25. 						visited=new boolean[n+2];
  26. 						Arrays.fill(visited, false);
  27.  
  28. 						for(int i=0;i<n+2;i++)
  29. 							graph[i]=new ArrayList<Integer>();
  30. 						//now for m different interactions
  31. 						for(int i=0;i<m;i++)
  32. 						{
  33. 							in=br.readLine().split(" ");
  34. 							int a=Integer.parseInt(in[0]);
  35. 							int b=Integer.parseInt(in[1]);
  36. 							graph[a].add(b);
  37. 							graph[b].add(a);
  38.  
  39. 						}
  40. 						boolean check=dfs(1);
  41.  
  42. 						if(!check)//
  43. 							System.out.println("Scenario #"+t+":\nSuspicious bugs found!");
  44. 						else
  45. 							System.out.println("Scenario #"+t+":\nNo suspicious bugs found!");
  46.  
  47.  
  48. 					}
  49.  
  50. 				}
  51.  
  52. 				static boolean dfs(int rootnode)
  53. 				{
  54. 					Stack<Integer> mystack =new Stack<Integer>();
  55. 					mystack.push(rootnode);
  56. 					colour[rootnode]=1;
  57. 					visited[rootnode]=true;
  58. 					while(!mystack.isEmpty())
  59. 					{
  60. 						int node=mystack.peek();
  61. 						int child=get_unvisited_uncoloured_childnode(node,colour[node]);
  62. 						if(child==Integer.MIN_VALUE)//may day may day 
  63. 							{return false;}
  64. 						else if(child==0)
  65. 							mystack.pop();
  66. 						else
  67. 							mystack.push(child);
  68.  
  69. 					}
  70.  
  71. 					return true;
  72. 				}
  73.  
  74. 				static int get_unvisited_uncoloured_childnode(int node,int base_colour)
  75. 				{
  76. 					//for each V in the adjacent list of u
  77. 					ArrayList<Integer> adj_list=graph[node];
  78. 					Iterator<Integer> it=adj_list.iterator();
  79. 					while(it.hasNext())
  80. 					{
  81. 						int hold=it.next();
  82. 						if(visited[hold]==false)//if hold is not yet visited
  83. 						{
  84. 							colour[hold]=base_colour*-1;
  85. 							visited[hold]=true;
  86. 							return hold;
  87. 						}
  88. 						else if(visited[hold]==true && colour[hold]==base_colour)
  89. 						{
  90. 							//not bipartite
  91. 							return Integer.MIN_VALUE;
  92. 						}
  93.  
  94. 					}
  95.  
  96.  
  97. 					return 0;
  98. 				}
  99. 			}
  100.  
  101.  
Success #stdin #stdout 0.08s 380160KB
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/F9NXIe
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!