fork download
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. int main() {
  6. int n;
  7. cin >> n;
  8.  
  9. unordered_map<int, vector<int>> G;
  10.  
  11. // Input edges
  12. for (int i = 0; i < n ; i++) {
  13. int a, b;
  14. cin >> a >> b;
  15.  
  16. G[a].push_back(b);
  17. }
  18.  
  19. // Queue and visited array
  20. queue<int> q;
  21. vector<bool> visited(n + 1, false);
  22.  
  23. // count array
  24. vector<int> cnt(n+1, 0);
  25.  
  26. // Insert root (1)
  27. q.push(1);
  28. visited[1] = true;
  29.  
  30. // BFS traversal
  31. while (!q.empty()) {
  32. int front = q.front();
  33. q.pop();
  34.  
  35. int count = 0;
  36.  
  37. cout << front << " ";
  38.  
  39. for (int child : G[front]) {
  40. if (!visited[child]) {
  41. visited[child] = true;
  42. q.push(child);
  43. count++;
  44. }
  45. }
  46.  
  47. cnt[front] = count;
  48. }
  49.  
  50.  
  51. cout<<endl;
  52.  
  53. for(int i=1; i<=n+1; i++){
  54. cout<<"children of "<< i<< ": " << cnt[i] << "\n";
  55.  
  56. }
  57.  
  58. cout<<"leaf nodes \n";
  59.  
  60. for(int i=1; i<=n+1; i++){
  61. if(cnt[i]==0){
  62. cout<< i<<" ";
  63. }
  64. }
  65.  
  66. return 0;
  67. }
Success #stdin #stdout 0s 544KB
stdin
5
1 2
1 3
2 4
2 5
3 6
stdout
1 2 3 4 5 6 
children of 1: 2
children of 2: 2
children of 3: 1
children of 4: 0
children of 5: 0
children of 6: 0
leaf nodes 
4 5 6