fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3.  
  4. /*
  5.  
  6. 7
  7. 6
  8. 1 2
  9. 1 3
  10. 2 4
  11. 2 5
  12. 3 6
  13. 3 7
  14.  
  15. case 2:-
  16. 2
  17. 1
  18. 1 2
  19.  
  20. cas 3:-
  21. 1
  22. 0
  23.  
  24. */
  25.  
  26.  
  27. import java.util.*;
  28. import java.lang.*;
  29. import java.io.*;
  30.  
  31. /* Name of the class has to be "Main" only if the class is public. */
  32. class Ideone
  33. {
  34. 	public static void main (String[] args) throws java.lang.Exception
  35. 	{
  36. 		Scanner sc = new Scanner(System.in);
  37. 		int n = sc.nextInt();
  38. 		int m = sc.nextInt();
  39. 		List<List<Integer>> adj = new ArrayList<>();
  40. 		for(int i=0; i<=n;i++){
  41. 			adj.add(new ArrayList<>());
  42. 		}
  43.  
  44. 		for(int i=0; i<m; i++){
  45. 			int u = sc.nextInt();
  46. 			int v = sc.nextInt();
  47. 			adj.get(u).add(v);
  48. 			adj.get(v).add(u);
  49. 		}
  50.  
  51. 		List<Integer> leaves = printLeafBfs(adj,1);
  52. 		System.out.println(leaves);
  53.  
  54. 	}
  55.  
  56. 	public static List<Integer> printLeafBfs(List<List<Integer>> adj,int src){
  57.  
  58. 		Queue<Integer> q = new LinkedList<>();
  59. 		boolean visited[] = new boolean[adj.size()];
  60. 		q.add(src);
  61. 		visited[src] = true;
  62. 		List<Integer> leaves = new ArrayList<>();
  63. 		if(adj.get(src).isEmpty()){
  64. 			leaves.add(src);
  65. 			return leaves;
  66. 		}
  67.  
  68. 		while(!q.isEmpty()){
  69. 			int cur = q.poll();
  70. 			// System.out.print(cur);
  71.  
  72. 			if( (adj.get(cur).size()==1 && visited[adj.get(cur).get(0)])){
  73. 				leaves.add(cur);
  74. 			}
  75. 			for(int x : adj.get(cur)){
  76. 				if(!visited[x]){
  77. 					q.add(x);
  78. 					visited[x] = true;
  79. 				}
  80. 			}
  81. 		}
  82.  
  83. 		return leaves;
  84.  
  85. 	}
  86.  
  87. 		public static List<Integer> printLeafBfsAlgo2(List<List<Integer>> adj,int src){
  88.  
  89. 		Queue<Integer> q = new LinkedList<>();
  90. 		boolean visited[] = new boolean[adj.size()];
  91. 		q.add(src);
  92. 		visited[src] = true;
  93. 		List<Integer> leaves = new ArrayList<>();
  94. 		int child[]=new int[adj.size()];
  95. 		if(adj.get(src).isEmpty()){
  96. 			leaves.add(src);
  97. 			return leaves;
  98. 		}
  99.  
  100. 		while(!q.isEmpty()){
  101. 			int cur = q.poll();
  102.  
  103. 			int c=0;
  104. 			for(int x : adj.get(cur)){
  105. 				if(!visited[x]){
  106. 					q.add(x);
  107. 					visited[x] = true;
  108. 					c++;
  109. 				}
  110. 			}
  111.  
  112. 			child[cur]=c;
  113. 		}
  114.  
  115. 		for(int i=1; i<child.length;i++){
  116. 			if(child[i] == 0){
  117. 				leaves.add(i);
  118. 			}
  119. 		}
  120.  
  121. 		return leaves;
  122.  
  123. 	}
  124.  
  125. 	public static List<Integer> printLeafdfs(){
  126.  
  127. 		return new ArrayList<>();
  128. 	}
  129. }
Success #stdin #stdout 0.13s 54576KB
comments (?)
stdin
copy 
1
0
stdout
copy 
[1]
https://ideone.com/6lRKou
language:
Java (HotSpot 12)
created:
3 days 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!