Cod sursa(job #2155742)

Utilizator savigunFeleaga Dragos-George savigun Data 8 martie 2018 01:52:19
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int MAXN = 100005;
int n, m, t, time[MAXN], low[MAXN], ncb;
bool viz[MAXN];
vector<int> g[MAXN];
vector<int> cb[MAXN];
stack<int> st;

void save_cb(int x) {
    ncb++;
    while (st.top() != x) {
        cb[ncb].push_back(st.top());
        st.pop();
    }
    cb[ncb].push_back(x);
}

void dfs(int x, int px) {
    viz[x] = true;
    time[x] = ++t;
    low[x] = time[x];
    st.push(x);

    for (int &y : g[x]) {
        if (y == px) continue;
        if (!viz[y]) {
            dfs(y, x);
            low[x] = min(low[x], low[y]);
            if (low[y] >= time[x]) {
                save_cb(x);
            }
        } else {
            low[x] = min(low[x], time[y]);
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i = 1, x, y; i <= m; ++i) {
        in >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            dfs(i, -1);
        }
    }

    out << ncb << "\n";

    for (int i = 1; i <= ncb; ++i) {
        sort(cb[i].begin(), cb[i].end(), less<int>());
        for (int &y : cb[i]) out << y << " ";
        out << "\n";
    }

    return 0;
}