Cod sursa(job #1909220)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 7 martie 2017 11:56:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vb = vector<bool>;

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

int n, m;
stack<pii> stk;
vector<vi> biconexe;
vector<vi> v;
vi lev, levMin;
vi comp;
vb seen;

inline void read() {
    fin >> n >> m;
    v = vector<vi>(n + 1);
    lev = levMin = vi(n + 1);
    seen = vb(n + 1);
    for (int i = 1, x, y; i <= m; ++i) {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void dfs(int node, int father) {
    lev[node] = levMin[node] = lev[father] + 1;
    seen[node] = 1;
    int x1, x2;
    for (const int& x: v[node]) {
        if (x == father)
            continue;
        if (!seen[x]) { // tree edge
            stk.push({node, x});
            dfs(x, node);
            levMin[node] = min(levMin[node], levMin[x]);
            if (levMin[x] >= lev[node]) {
                comp.clear();
                do {
                    x1 = stk.top().first, x2 = stk.top().second;
                    stk.pop();
                    comp.push_back(x1);
                    comp.push_back(x2);
                } while (x1 != node && x2 != x);
                biconexe.push_back(comp);
            }
        }
        else
            levMin[node] = min(levMin[node], lev[x]);
    }
}

inline void write() {
    fout << biconexe.size() << '\n';
    for (auto& cc: biconexe) {
        sort(cc.begin(), cc.end());
        cc.erase(unique(cc.begin(), cc.end()), cc.end());
        for (const int& x: cc)
            fout << x << ' ';
        fout << '\n';
    }
}

int main()
{
    read();
    dfs(1, 0);
    write();

    fin.close();
    fout.close();
    return 0;
}