Cod sursa(job #2199341)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 27 aprilie 2018 11:58:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
#define dimn 100005
#define mp std::make_pair
using data = std::pair <int, int>;

std::ifstream f("biconex.in");
std::ofstream g("biconex.out");

int N;
std::vector <int> comp[dimn];
std::list <int> adj[dimn];
std::stack <data> s;
int ord[dimn], lowlink[dimn];
int nrb;

int lvl = 1;
void dfs(int start=1) {
    ord[start] = lowlink[start] = lvl++;

    for (auto vec:adj[start]) {
        if(!ord[vec]) {
            s.push(mp(start, vec));
            dfs(vec);

            lowlink[start] = std::min(lowlink[start], lowlink[vec]);
            if(lowlink[vec] >= ord[start]) {
                nrb++;
                while(s.top().first != start)
                    comp[nrb].push_back(s.top().second),
                    s.pop();
                comp[nrb].push_back(s.top().first);
                comp[nrb].push_back(s.top().second);
                s.pop();
                std::sort(comp[nrb].begin(), comp[nrb].end());
            }
        }
        else
            lowlink[start] = std::min(lowlink[start], ord[vec]);
    }
}

void citire() {
    f >> N;
    int M; f >> M;
    for (int i=0, y, x; i<M; i++) {
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}
void rezolvare() {
    for (int i=1; i<=N; i++)
        if(!ord[i])
            dfs(i);

    g << nrb << "\n";
    for (int i=1, j; i<=nrb; i++) {
        for (j=0; j<comp[i].size(); j++)
            g << comp[i][j] << " ";
        g << "\n";
    }
}

int main()
{
    citire();
    rezolvare();

    return 0;
}