Guest User

MDST

a guest
Sep 12th, 2020
31
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int>pii;
  4. #define sf(x) scanf("%d",&x)
  5. #define sfl(x) scanf("%lld",&x)
  6. #define lli long long int
  7. #define ll64 int64_t
  8. #define pb push_back
  9. #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  10. #define frr(i,a) for(int i=0;i<a;i++)
  11. #define frl(i,a) for(lli i=0;i<a;i++)
  12. const int mx=1004;
  13. vector<bool>vis;
  14. vector<int>adj[mx],dis,mst[mx];
  15. int n;
  16. void Bfs(int u)
  17. {
  18. queue<int>q;
  19. q.push(u);
  20. vis[u]=true;
  21. while(!q.empty())
  22. {
  23. int v=q.front();
  24. //cout<<"v = "<<v<<endl;
  25. q.pop();
  26. for(int i=0;i<adj[v].size();i++)
  27. {
  28. int x=adj[v][i];
  29. if(!vis[x])
  30. {
  31. //cout<<"x = "<<x<<" ";
  32. mst[v].pb(x);
  33. mst[x].pb(v);
  34. dis[x]=dis[v]+1;
  35. vis[x]=true;
  36. q.push(x);
  37. }
  38. }
  39. //cout<<endl;
  40. }
  41. return ;
  42. }
  43. void bfs(int u)
  44. {
  45. for(int i=1;i<=n+2;i++)
  46. {
  47. mst[i].clear();
  48. }
  49. vis=vector<bool>(n+4,false);
  50. dis=vector<int>(n+4,0);
  51. return Bfs(u);
  52. }
  53. void Dfs(int u)
  54. {
  55. vis[u]=true;
  56. for(int i=0;i<mst[u].size();i++)
  57. {
  58. int x=mst[u][i];
  59. if(!vis[x])
  60. {
  61. dis[x]=dis[u]+1;
  62. Dfs(x);
  63. }
  64. }
  65. return;
  66. }
  67. void dfs(int u)
  68. {
  69. /*for(int i=1;i<=n+2;i++)
  70. {
  71. for(int j=0;j<mst[i].size();j++)
  72. {
  73. cout<<mst[i][j]<<" ";
  74. }
  75. cout<<endl;
  76. }*/
  77. vis=vector<bool>(n+4,false);
  78. dis=vector<int>(n+4,0);
  79. return Dfs(u);
  80. }
  81. int main()
  82. {
  83. int t;
  84. sf(t);
  85. while(t--)
  86. {
  87. vector<pii>edge;
  88. int m,u,v,dm=INT_MAX;
  89. sf(n);
  90. for(int j=1;j<=n;j++)
  91. {
  92. sf(u);
  93. sf(m);
  94. for(int k=0;k<m;k++)
  95. {
  96. sf(v);
  97. adj[u].pb(v);
  98. edge.pb({u,v});
  99. }
  100. }
  101. for(int i=1;i<=n;i++)
  102. {
  103. bfs(i);
  104. int mx=-1,l;
  105. for(int j=1;j<=n;j++)
  106. {
  107. if(dis[j]>mx)
  108. {
  109. mx=dis[j];
  110. l=j;
  111. }
  112. }
  113. dfs(l);
  114. mx=-1;
  115. for(int j=1;j<=n;j++)
  116. {
  117. if(dis[j]>mx)
  118. {
  119. mx=dis[j];
  120. }
  121. }
  122. dm=min(dm,mx);
  123. }
  124. //cout<<"dm = "<<dm<<endl;
  125. for(int i=0;i<edge.size();i++)
  126. {
  127. u=edge[i].first;
  128. v=edge[i].second;
  129. //cout<<"u = "<<u<<" v = "<<v<<endl;
  130. adj[n+2].pb(u);
  131. adj[n+2].pb(v);
  132. bfs(n+2);
  133. int mx=-1,l;
  134. for(int j=1;j<=n+2;j++)
  135. {
  136. if(dis[j]>mx)
  137. {
  138. mx=dis[j];
  139. l=j;
  140. }
  141. }
  142. dfs(l);
  143. mx=-1;
  144. for(int j=1;j<=n+2;j++)
  145. {
  146. if(dis[j]>mx)
  147. {
  148. mx=dis[j];
  149. }
  150. }
  151. adj[n+2].pop_back();
  152. adj[n+2].pop_back();
  153. //cout<<u<<" "<<v<<" "<<mx<<endl;
  154. dm=min(dm,mx-1);
  155. }
  156. printf("%d\n",dm);
  157. for(int i=1;i<=n+2;i++)
  158. {
  159. adj[i].clear();
  160. }
  161. }
  162. }
  163.  
RAW Paste Data