bhupixb

Number of nodes in subtree of a node including itself

Aug 2nd, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.65 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1e5+8;
  4. int vis[N], dist[N];
  5. vector < int > v[N], vv[N];
  6. long int dfs(int node){
  7. vis[node]= 1;
  8. long int cnt = 0;
  9. for(auto i : v[node]){
  10. if(!vis[i]){
  11. cnt = cnt + dfs(i);
  12. }
  13. }
  14. if(!cnt)return dist[node] = 1;
  15. else
  16. return dist[node] = ++cnt;
  17. }
  18. int main(){
  19. int m, n, j, i, l, r, a(0), b(0);
  20. scanf("%d %d", &n ,&m);
  21.  
  22. for(i = 0; i < m; i++){
  23. scanf("%d%d", &l, &r);
  24. v[l].push_back(r);
  25. v[r].push_back(l);
  26. }
  27.  
  28. dfs(1);
  29. for(i = 1; i <= n; i++)cout << dist[i] << ' ';
  30. return 0;
  31. }
Add Comment
Please, Sign In to add comment