lalalalalalalaalalla

Untitled

Sep 19th, 2019
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void bfs(int v) {
  2. queue<int> q;
  3. q.push(v);
  4. while (!q.empty()) {
  5. v = q.front();
  6. q.pop();
  7. for (auto u: ng[v]) {
  8. if (d[u] > d[v] + 1) {
  9. d[u] = d[v] + 1;
  10. q.push(u);
  11. }
  12. }
  13. }
  14. }
  15.  
  16. d.assign(comp, INF);
  17. for (int i = 0; i < comp; i++) {
  18. if (d[i] == INF) {
  19. d[i] = 0;
  20. bfs(i);
  21. }
  22. }
  23. int start = 0;
  24. vector<int> check = {start};
  25. for (int i = 1; i < comp; i++) {
  26. if (d[i] > d[start]) {
  27. check.clear();
  28. check.pb(i);
  29. start = i;
  30. } else if (d[i] == d[start]) {
  31. check.pb(i);
  32. }
  33. }
  34. d.assign(comp, INF);
  35. for (auto k: check) {
  36. if (d[k] == INF) {
  37. d[k] = 0;
  38. bfs(k);
  39. }
  40. }
  41. int dd = 0;
  42. for (int i = 0; i < comp; i++) {
  43. if (d[i] != INF && d[i] > dd) dd = d[i];
  44. }
RAW Paste Data