Advertisement
Guest User

Untitled

a guest
Jun 27th, 2016
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:10000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <cstdio>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. vector< vector<int> > graph;
  10. vector<int> articulation_point;
  11. bool *used;
  12. int time, *tin;
  13.  
  14. int dfs(int v, int p = -1)
  15. {
  16. bool v_used = false;
  17. used[v] = true;
  18. tin[v] = time++;
  19. int min_time = tin[v];
  20. int children = 0;
  21. for (size_t i = 0; i < graph[v].size(); ++i)
  22. {
  23. int to = graph[v][i];
  24. if (to == p)
  25. continue;
  26. if (used[to])
  27. min_time = min(min_time, tin[to]);
  28. else
  29. {
  30. int b = dfs(to, v);
  31. min_time = min(min_time, b);
  32. if (b >= tin[v] && p != -1)
  33. {
  34. if (!v_used)
  35. articulation_point.push_back(v);
  36. v_used = true;
  37. }
  38. ++children;
  39. }
  40. }
  41. if (p == -1 && children > 1)
  42. {
  43. if (!v_used)
  44. articulation_point.push_back(v);
  45. v_used = true;
  46. }
  47. return min_time;
  48. }
  49.  
  50. int main()
  51. {
  52. FILE *fin = fopen("input.txt", "r");
  53. FILE *fout = fopen("output.txt", "w");
  54. int n, m;
  55. fscanf(fin, "%d%d", &n, &m);
  56. graph.resize(n);
  57. tin = new int[n];
  58. used = new bool[n];
  59. for (int i = 0; i < n; ++i)
  60. {
  61. tin[i] = -1;
  62. used[i] = false;
  63. }
  64. for (int i = 0; i < m; ++i)
  65. {
  66. int buff1, buff2;
  67. fscanf(fin, "%d%d", &buff1, &buff2);
  68. graph[--buff1].push_back(--buff2);
  69. graph[buff2].push_back(buff1);
  70. }
  71. fclose(fin);
  72. dfs(0);
  73. delete[] tin;
  74. delete[] used;
  75. fprintf(fout, "%d ", articulation_point.size());
  76. for (vector<int>::iterator i = articulation_point.begin(); i != articulation_point.end(); ++i)
  77. fprintf(fout, "%d ", *i + 1);
  78. fclose(fout);
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement