Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:10000000")
- #define _CRT_SECURE_NO_WARNINGS
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector< vector<int> > graph;
- vector<int> articulation_point;
- bool *used;
- int time, *tin;
- int dfs(int v, int p = -1)
- {
- bool v_used = false;
- used[v] = true;
- tin[v] = time++;
- int min_time = tin[v];
- int children = 0;
- for (size_t i = 0; i < graph[v].size(); ++i)
- {
- int to = graph[v][i];
- if (to == p)
- continue;
- if (used[to])
- min_time = min(min_time, tin[to]);
- else
- {
- int b = dfs(to, v);
- min_time = min(min_time, b);
- if (b >= tin[v] && p != -1)
- {
- if (!v_used)
- articulation_point.push_back(v);
- v_used = true;
- }
- ++children;
- }
- }
- if (p == -1 && children > 1)
- {
- if (!v_used)
- articulation_point.push_back(v);
- v_used = true;
- }
- return min_time;
- }
- int main()
- {
- FILE *fin = fopen("input.txt", "r");
- FILE *fout = fopen("output.txt", "w");
- int n, m;
- fscanf(fin, "%d%d", &n, &m);
- graph.resize(n);
- tin = new int[n];
- used = new bool[n];
- for (int i = 0; i < n; ++i)
- {
- tin[i] = -1;
- used[i] = false;
- }
- for (int i = 0; i < m; ++i)
- {
- int buff1, buff2;
- fscanf(fin, "%d%d", &buff1, &buff2);
- graph[--buff1].push_back(--buff2);
- graph[buff2].push_back(buff1);
- }
- fclose(fin);
- dfs(0);
- delete[] tin;
- delete[] used;
- fprintf(fout, "%d ", articulation_point.size());
- for (vector<int>::iterator i = articulation_point.begin(); i != articulation_point.end(); ++i)
- fprintf(fout, "%d ", *i + 1);
- fclose(fout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement