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