Cod sursa(job #1977076)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 22:43:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100002

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

vector<int> graf[NMAX], biconexe[NMAX];

int nrBic = 0;
int ind[NMAX], lowlink[NMAX], idx = 0;

stack< pair<int, int> > stiva;

void getBicon(int nodex, int nodey) {

    int x, y;
    do {

        x = stiva.top().first;
        y = stiva.top().second;
        stiva.pop();

        biconexe[nrBic].push_back(x);
        biconexe[nrBic].push_back(y);

    }while(make_pair(nodex, nodey) != make_pair(x, y));

    nrBic++;
}

void DFS(int node) {

    ind[node] = lowlink[node] = ++idx;

    for (auto& adj: graf[node]) {

        if (!ind[adj]) {

            stiva.push(make_pair(node, adj));

            DFS(adj);
            lowlink[node] = min(lowlink[node], lowlink[adj]);

            if (ind[node] <= lowlink[adj])
                getBicon(node, adj);
        }
        else
            lowlink[node] = min(lowlink[node], ind[adj]);

    }


}

int main() {

    int N, M;

    fin >> N >> M;

    int x, y;
    while (M--) {

        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i)
        if (!ind[i])
            DFS(i);

    fout << nrBic << "\n";
    for (int i = 0; i < nrBic; ++i) {

        sort(biconexe[i].begin(), biconexe[i].end());
        biconexe[i].erase(unique(biconexe[i].begin(), biconexe[i].end()), biconexe[i].end());

        for (auto& node: biconexe[i])
            fout << node << " ";

        fout << "\n";
    }

    return 0;
}