Cod sursa(job #1620772)

Utilizator mariusn01Marius Nicoli mariusn01 Data 29 februarie 2016 12:41:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#define DIM 100010
using namespace std;

vector<int> L[DIM];
vector<int> C[DIM];
bitset<DIM> v;
stack<int> Stack;

int Niv[DIM], Low[DIM];

int n, m, i, x, y, cbc, j;

void dfs(int nod, int tata, int niv) {
    v[nod] = 1;
    Niv[nod] = niv;
    Low[nod] = niv;
    Stack.push(nod);

    for (vector<int>::iterator it = L[nod].begin(); it != L[nod].end(); it++) {
        if (nod == tata)
            continue;

        if (v[*it]) {
            Low[nod] = min(Low[nod], Niv[*it]);
            continue;
        }

        dfs(*it, nod, niv+1);
        Low[nod] = min(Low[nod], Low[*it]);
        if (Low[*it] >= Niv[nod]) {
            cbc++;
            //C.clear();
            do {
                x = Stack.top();
                Stack.pop();
                C[cbc].push_back(x);
            } while (x != *it);
            C[cbc].push_back(nod);
        }
    }

}

int main () {
    ifstream fin ("biconex.in");
    ofstream fout("biconex.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (i=1;i<=n;i++)
        if (v[i] == 0)
            dfs(i, 0, 1);

    fout<<cbc<<"\n";
    for (i=1;i<=cbc;i++) {
        for (j=0;j<C[i].size();j++)
            fout<<C[i][j]<<" ";
        fout<<"\n";
    }

    return 0;
}