Cod sursa(job #2668367)

Utilizator albertyoAlbert Mindrescu albertyo Data 4 noiembrie 2020 20:12:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#define N 100005

using namespace std;

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

int n, m, niv[N], up[N], viz[N], S[N], top, ct;
vector <int> muchii[N], cbi[N];

void DFS(int nod, int parinte) {

    viz[nod] = 1;
    up[nod] = niv[nod];
    S[++top] = nod;

    for( auto i: muchii[nod]) {

        if(i == parinte) continue;
        if(viz[i])
            up[nod] = min(up[nod], niv[i]);
        else {
            niv[i] = niv[nod] + 1;
            DFS(i, nod);
            if(up[i] >= niv[nod]) {

                ct++;
                while(top && S[top]!= i)
                    cbi[ct].push_back(S[top--]);
                cbi[ct].push_back(S[top--]);
                cbi[ct].push_back(nod);
            }
            up[nod] = min(up[nod], up[i]);
        }
    }
}

int main()
{
    int i, x, y;
    fin >> n >> m;

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

    DFS(1, 0);
    fout << ct << "\n";
    for(i = 1; i <= ct; i++) {

        for(auto j: cbi[i])
            fout << j << " ";

        fout << "\n";
    }

    return 0;
}