Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // 2.D
- //
- // Created by Andrey Chulkov on 7/29/15.
- // Copyright (c) 2015 Andrey Chulkov. All rights reserved.
- //
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <map>
- #include <algorithm>
- #define m_p make_pair
- using namespace std;
- typedef pair<int, int> int_pair;
- int t = 0;
- vector<int> tin;
- vector<int> tout;
- vector<bool> used;
- vector<vector<int_pair>> graph;
- vector<int> points;
- map<pair<int, int>, int> edge_id;
- const int N = 1e5 + 7;
- int dfs_fup(int v, int from) {
- int cnt = 0;
- bool done = false;
- int fup;
- used[v] = true;
- tin[v] = t;
- fup = tin[v];
- t += 1;
- for (auto u : graph[v]) {
- if (!used[u.first] && (u.second != from)) {
- cnt += 1;
- int fup_u;
- fup_u = dfs_fup(u.first, u.second);
- fup = min(fup_u, fup);
- if ((from != N) && (!done) && (tin[v] <= fup_u)) {
- points.push_back(v);
- done = true;
- }
- }
- else if (u.second != from) {
- fup = min(tin[u.first], fup);
- }
- }
- if ((from == N) && (!done) && (cnt > 1)) {
- points.push_back(v);
- }
- tout[v] = t;
- t += 1;
- return fup;
- }
- int main() {
- int n, m;
- cin >> n >> m;
- graph.assign(n, vector<int_pair>());
- used.assign(n, false);
- tin.resize(n);
- tout.resize(n);
- for (int i = 0; i < m; i ++) {
- int b_i, e_i;
- cin >> b_i >> e_i;
- graph[b_i - 1].push_back(m_p(e_i - 1, i));
- graph[e_i - 1].push_back(m_p(b_i - 1, i));
- edge_id[m_p(b_i - 1, e_i - 1)] = i + 1;
- edge_id[m_p(e_i - 1, b_i - 1)] = i + 1;
- }
- for (int v = 0; v < n; v ++) {
- if (!used[v]) {
- dfs_fup(v, N);
- }
- }
- int k;
- k = (int) points.size();
- cout << k << endl;
- sort(points.begin(), points.end());
- for (int i = 0; i < k; i ++) {
- cout << points[i] + 1 << " ";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment