Cod sursa(job #2225272)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 26 iulie 2018 15:10:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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 (!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)
{
    viz[nod] = 0;
    comp[c].push_back(nod);

    for (auto i : adia[nod]) {
        if (viz[i]) {
            if (up[i] < h[nod])
                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);
    }

    dfs(1);

    comp.push_back(vector <int> ());
    divide(1, 0);

    int s = 0;
    for (auto i : comp)
        s += i.size() != 1;

    out << s << '\n';

    for (auto i : comp) {
        if (i.size() == 1)
            continue;
        for (auto j : i)
            out << j << ' ';
        out << '\n';
    }

    return 0;
}