Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* */
- #include <vector>
- #include <iostream>
- #include <set>
- using namespace std;
- class Graph {
- public:
- explicit Graph(size_t v_amount) : graph(v_amount + 1), visited(v_amount + 1), tin(v_amount+1, v_amount+1),
- up(v_amount+1, v_amount+1), from(v_amount + 1), children(v_amount+1){
- }
- void add_e(size_t a, size_t b) {
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- vector<size_t> get_articulation_points(){
- time = 0;
- for(size_t v = 1; v < graph.size(); ++v){
- if (visited[v] == 0){
- dfs(v);
- if (children[v] < 2){
- art_points.erase(v);
- }
- }
- }
- art_points.erase(0);
- return {art_points.begin(), art_points.end()};
- }
- void dfs(size_t v){
- visited[v] = 1;
- ++time;
- tin[v] = time;
- for (auto neighbour : graph[v]){
- if (visited[neighbour] == 0){
- from[neighbour] = v;
- children[v]++;
- dfs(neighbour);
- up[v] = min(up[v], up[neighbour]);
- if (up[neighbour] >= tin[v]){
- art_points.insert(v);
- }
- }
- if (visited[neighbour] == 1 && from[v] != neighbour){
- up[v] = min(up[v], tin[neighbour]);
- }
- }
- visited[v] = 2;
- }
- vector<size_t> children;
- vector<size_t> from;
- set<size_t> art_points;
- size_t time;
- vector<size_t> tin;
- vector<size_t> up;
- vector<int> visited;
- vector<vector<size_t>> graph;
- };
- int main(){
- size_t v_amount, e_amount;
- cin >> v_amount >> e_amount;
- Graph graph(v_amount);
- for (int i = 0; i < e_amount; ++i){
- size_t a, b;
- cin >> a >> b;
- graph.add_e(a, b);
- }
- auto ap = graph.get_articulation_points();
- cout << ap.size() << endl;
- for (auto v : ap){
- cout << v << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement