Cod sursa(job #2796480)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 noiembrie 2021 11:30:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N = 100010;

vector<int> v[N], ans[N];
int intoarcere[N], nivel[N], viz[N], st[N];
int top, nr_sol, n, m, x, y;

void dfs(int nod, int tata) {
    intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
    viz[nod] = 1;
    top++;
    st[top] = nod;

    for (auto fiu: v[nod]) {
        if (fiu == tata)
            continue;
        if (viz[fiu]) // suntem intr-o muchie de intoarcere
        {
            intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
            continue;
        }

        dfs(fiu, nod);
        intoarcere[nod] = min(intoarcere[nod], intoarcere[fiu]);

        if (intoarcere[fiu] >= nivel[nod]) {
            nr_sol++;
            while (st[top + 1] != fiu) {
                ans[nr_sol].push_back(st[top]);
                top--;
            }
            ans[nr_sol].push_back(nod);
        }

    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i, 0);
    fout << nr_sol << '\n';
    for (int i = 1; i <= nr_sol; i++) {
        for (auto it: ans[i])
            fout << it << " ";
        fout << '\n';
    }

    return 0;
}