Cod sursa(job #1576068)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 22 ianuarie 2016 01:11:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

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

const int NMAX = 1e5 + 1;

int N, M, root, cnt;
vector<int> v[NMAX]; // graf
vector<vector<int> > biconexe;
vector<int> c;
stack<pair<int, int> > s;
bool viz[NMAX];
int L[NMAX], niv[NMAX];

void dfs(int nod, int tata) {
    L[nod] = niv[nod] = niv[tata] + 1;
    viz[nod] = 1;
    int x1, x2;
    for (const int& x: v[nod]) {
        if (x == tata) // sarim peste tata
            continue;
        if (!viz[x]) { // muchie de arbore
            s.push({nod, x});
            dfs(x, nod);
            L[nod] = min(L[nod], L[x]);
            if (L[x] >= niv[nod]) {
                c.clear();
                do {
                    x1 = s.top().first;
                    x2 = s.top().second;
                    s.pop();
                    c.push_back(x1);
                    c.push_back(x2);
                } while(x1 != nod && x2 != x);
                biconexe.push_back(c);
            }
        }
        else { // muchie de intoarcere
            L[nod] = min(L[nod], niv[x]);
        }
    }
}

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

int main() {
    fin >> N >> M;
    for (int x, y; M; --M) {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    write();
    fin.close();
    fout.close();
    return 0;
}