Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <numeric>
- #include <set>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <climits>
- #include <string>
- #include <cstdio>
- #include <cmath>
- #define task "TESTCODE"
- using namespace std;
- const int N = 1e5;
- vector<vector<int>> Adj;
- int n, m, x, y, Count = 0, Number[N+1], Low[N+1];
- bool CritNode[N+1];
- vector<int> criticalnodes;
- void read()
- {
- cin >> n >> m;
- Adj.resize(n+1);
- while (m -- )
- {
- cin >> x >> y;
- Adj[x].push_back(y);
- Adj[y].push_back(x);
- }
- fill (CritNode, CritNode + n + 1, false);
- }
- void Visit (int u, int p)
- {
- int Numchild = 0;
- ++Count;
- Low[u] = Number[u] = Count;
- for (int v : Adj[u])
- {
- if (v != p)
- {
- if (Number[v] != 0)
- {
- Low[u] = min(Low[u], Number[v]);
- }
- else
- {
- Visit(v, u);
- ++Numchild;
- Low[u] = min(Low[u], Low[v]);
- if (u == p)
- {
- if (Numchild >= 2)
- {
- CritNode[u] = true;
- }
- }
- else
- {
- if (Low[v] >= Number[u])
- {
- CritNode[u] = true;
- }
- }
- if (Low[v] >= Number[v])
- {
- cout << u << ' '<< v << '\n';
- }
- }
- }
- }
- }
- void solve()
- {
- for (int i = 1; i <= n; ++ i)
- {
- if (Number[i] == 0)
- {
- Visit(i, i);
- }
- }
- for (int i = 1; i <= n; ++ i)
- {
- if (CritNode[i])
- {
- criticalnodes.push_back(i);
- }
- }
- cout << criticalnodes.size() << '\n';
- for (int i : criticalnodes)
- {
- cout << i << ' ';
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- freopen(task".INP", "r", stdin);
- //freopen(task".OUT", "w", stdout);
- read();
- solve();
- }
Add Comment
Please, Sign In to add comment