fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. // your code goes here
  6. int n, m;
  7. cin >> n >> m;
  8. vector<vector<int>> matrix(n+5);
  9.  
  10. for (int i = 1; i <= m; i++){
  11. int a, b;
  12. cin >> a >> b;
  13. matrix[a].push_back(b);
  14. matrix[b].push_back(a);
  15. }
  16.  
  17. int source = 1; // here we are taking source as 1 because our input will be as source 1.
  18. // this source will only work with our input.
  19. // for another input we have to change our source.
  20.  
  21. // vector<int> used(n+5,0);
  22. unordered_map<int, int> used;
  23. queue<int> q;
  24. q.push(source);
  25.  
  26. used[source] = 1;
  27. vector<int> leaves;
  28.  
  29. while(!q.empty()){
  30. int removed = q.front();
  31.  
  32. q.pop();
  33. int count = 0;
  34.  
  35. for (int i : matrix[removed]){
  36. if(used[i] == 0){
  37. q.push(i);
  38. used[i] = 1;
  39. count += 1;
  40. }
  41. }
  42.  
  43. if(count == 0) leaves.push_back(removed);
  44.  
  45. cout << "The children of node " << removed << " are: " << count << endl;
  46. }
  47.  
  48. cout << endl << "The leaf Nodes are:- " << endl;
  49.  
  50. for (int i : leaves){
  51. cout << i << " ";
  52. }
  53.  
  54.  
  55. return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
stdin
11 10
1 2
1 5
1 7
2 3
2 4
5 6
7 8
7 9
7 11
9 10
stdout
The children of node 1 are: 3
The children of node 2 are: 2
The children of node 5 are: 1
The children of node 7 are: 3
The children of node 3 are: 0
The children of node 4 are: 0
The children of node 6 are: 0
The children of node 8 are: 0
The children of node 9 are: 1
The children of node 11 are: 0
The children of node 10 are: 0

The leaf Nodes are:- 
3 4 6 8 11 10