Cod sursa(job #2237119)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 31 august 2018 18:06:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e5 + 7;

vector < int > adia[N];

vector < vector < int > > comp;

bool viz[N];

int up[N], h[N];

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

void new_comp(int nod, int no) {
    comp[no].push_back(nod);
    viz[nod] = false;
    for (int i : adia[nod])
        if (viz[i]) {
            if (up[i] < h[nod])
                new_comp(i, no);
            else {
                comp.push_back({nod});
                new_comp(i, comp.size() - 1);
            }
        }
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    while (m--)
        cin >> 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])
            comp.push_back(vector < int > ()),
            new_comp(i, comp.size() - 1);
    }
    int s(0);
    for (auto i : comp)
        if (i.size() - 1)
            ++s;
    cout << s << '\n';
    for (auto i : comp) {
        if (i.size() - 1) {
            for (int elm : i)
                cout << elm << ' ';
            cout << '\n';
        }
    }
    return 0;
}