Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- vector < vector <ll> > adj(801);
- stack <ll> st;
- ll n, m, cnt = 0, res = 0, number[801], low[801];
- bool fr[801];
- void dfs(ll u) {
- number[u] = low[u] = cnt++;
- st.push(u);
- for (int i = 0; i < adj[u].size(); i++)
- if (fr[adj[u][i]]) {
- if (number[adj[u][i]]) low[u] = min(low[u], number[adj[u][i]]);
- else {
- dfs(adj[u][i]);
- low[u] = min(low[u], low[adj[u][i]]);
- }
- }
- if (number[u] == low[u]) {
- res++;
- ll v = st.top();
- st.pop();
- fr[v] = false;
- while (v != u) {
- cout << v << " ";
- v = st.top();
- st.pop();
- fr[v] = false;
- }
- cout << u << endl;
- }
- }
- int main() {
- freopen("test.inp", "r", stdin);
- freopen("test.out", "w", stdout);
- cin >> n >> m;
- for (int i = 1; i <= m; i++) {
- ll u, v;
- cin >> u >> v;
- adj[u].push_back(v);
- }
- memset(fr, true, sizeof(fr));
- for (int i = 1; i <= m; i++)
- if (fr[i]) dfs(i);
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement