Cod sursa(job #2650005)

Utilizator razviii237Uzum Razvan razviii237 Data 17 septembrie 2020 09:16:24
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

const int maxn = 1e5+5, inf = 1 << 30;

int n, m, x, y;

vector <int> nod[maxn];
vector < vector<int> > ans;

int seen[maxn], low[maxn], st[maxn];
int now, cnt;

void dfs(int x, int p) {
    st[++now] = x;
    low[x] = seen[x] = cnt++;
    for(auto u : nod[x]) {
        if(seen[u] == false) {
            int ptr = now;
            dfs(u, x);
            if(low[u] >= seen[x]) {
                vector<int> res = {x};
                while(ptr < now) {
                    res.push_back(st[now--]);
                }
                ans.push_back(res);
            }
            low[x] = min(low[u], low[x]);
        }
        else if(u != p) {
            low[x] = min(low[x], seen[u]);
        }
    }
}

int main()
{
    int i;

    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }

    dfs(1, 0);

    g << ans.size() << '\n';
    for(auto res : ans) {
        for(auto u : res) {
            g << u << ' ';
        }
        g << '\n';
    }

    f.close(); g.close();
    return 0;
}