Cod sursa(job #2668122)

Utilizator marianeacsuNeacsu Maria marianeacsu Data 4 noiembrie 2020 15:18:15
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 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 (i == y) continue;
        if (viz[i] == 1)
        {
      
            if (niv[i] < v[x]) 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 (niv[i] < v[x]) v[x] = niv[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;
}