Advertisement
nicuvlad76

Untitled

Feb 26th, 2023
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cstring>
  5. #define N 100005
  6. using namespace std;
  7.  
  8. ifstream fin("smallworld.in");
  9. ofstream fout("smallworld.out");
  10.  
  11. int n;
  12. int hmax[N];
  13. int dtop[N], T[N];
  14. vector <int> a[N];
  15.  
  16. void citire() {
  17. fin >> n;
  18. for(int i = 1; i < n; ++i) {
  19. int p, q;
  20. fin >> p >> q;
  21. a[p].push_back(q);
  22. a[q].push_back(p);
  23. }
  24. }
  25.  
  26. bool viz[N];
  27.  
  28. void DFS(int x) {
  29. viz[x] = 1;
  30. bool check = 0;
  31. int m = 0;
  32. for(auto &i : a[x])
  33. if(!viz[i]){
  34. check = 1;
  35. DFS(i);
  36. T[i]=x;
  37. m = max(m, hmax[i]);
  38. }
  39. if(!check)
  40. hmax[x] = 0;
  41. else
  42. hmax[x] = m + 1;
  43. }
  44.  
  45. void BFS(int x) {
  46. queue < int > q;
  47. q.push(x);
  48. dtop[x] = hmax[x];
  49. viz[x] = 1;
  50. while(!q.empty()) {
  51. int nod = q.front();
  52. q.pop();
  53. int frmax=0;
  54. for(auto &i:a[nod])
  55. if(!viz[i] && frmax<hmax[i])frmax=hmax[i];
  56.  
  57. for(auto &i: a[nod]) {
  58. if(!viz[i]) {
  59. dtop[i]=max(dtop[T[i]]+1, frmax);
  60. viz[i]=1;
  61. q.push(i);
  62. }
  63. }
  64. }
  65. }
  66. int main()
  67. {
  68. citire();
  69. DFS(1);
  70. memset(viz, 0, n+1);
  71. BFS(1);
  72. for(int i=1;i<=n;i++)
  73. fout<<dtop[i]<<"\n";
  74. return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement