Cod sursa(job #2668128)

Utilizator marianeacsuNeacsu Maria marianeacsu Data 4 noiembrie 2020 15:26:54
Problema Componente biconexe Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#define N 100005

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

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

void Citire()
{
    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);

    }
}

void DFS(int x, int y)
{
    viz[x] = 1;
    v[x] = niv[x];
    S[++top] = x;
    for (auto i : muchii[x])
    {
        if (viz[i] == 1)
        {
            if (v[x] > niv[i])
                v[x] = niv[i];
        }
        else
        {
            niv[i] = niv[x] + 1;
            DFS(i, x);
            if (v[i] >= niv[x])
            {
                ct++;
                while (top != 0 && S[top] != i)
                {
                    sol[ct].push_back(S[top--]);
                    sol[ct].push_back(S[top--]);
                    sol[ct].push_back(x);

                }
            }
            if (v[x] > v[i]) v[x] = v[i];

        }


    }
}




int main()
{
    int i;
    Citire();
    DFS(1, 0);
    fout << ct << "\n";
    for (i = 1; i <= ct; i++)
    {
        for (auto it : sol[i])
        {
            fout << it << " ";
            fout << "\n";
        }

    }
    return 0;
}