Cod sursa(job #2225269)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 26 iulie 2018 15:04:02
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;

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

int up[100010];
int h[100010];
bool viz[100010];
vector <int> adia[100010];
vector <vector <int>> comp;

void dfs(int nod, int tata = 0)
{
    viz[nod] = 1;
    up[nod] = h[nod];
    for (auto i : adia[nod]) {
        if (i == tata) {
            tata = -1;
            continue;
        }
        if (!viz[i]) {
            h[i] = 1 + h[nod];
            dfs(i, nod);
            up[nod] = min(up[nod], up[i]);
        }
        up[nod] = min(up[nod], h[i]);
    }
}

void divide(int nod, int c, bool tata = true)
{
    viz[nod] = 0;
    comp[c].push_back(nod);

    for (auto i : adia[nod]) {
        if (viz[i]) {
            if (up[i] < h[nod] || (up[i] == h[nod] && !tata))
                divide(i, c);
            else {
                comp.push_back({ nod });
                divide(i, comp.size() - 1);
            }
        }
    }
}

int main()
{
    int n, m, a, b;
    in >> n >> m;

    while (m--) {
        in >> a >> b;
        adia[a].push_back(b);
        adia[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);

    for (int i = 1; i <= n; i++) {
        if (viz[i]) {
            assert(i == 1);
            comp.push_back(vector <int> ());
            divide(i, comp.size() - 1, 0);
        }
    }

    out << comp.size() << '\n';

    for (auto i : comp) {
        for (auto j : i)
            out << j << ' ';
        out << '\n';
    }

    return 0;
}