Cod sursa(job #2102473)

Utilizator vasilicamoldovanVasilica Moldovan vasilicamoldovan Data 8 ianuarie 2018 21:25:16
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;

const int Inf = 0x3f3f3f3f;

VVI G, f, comp;
VI niv, t, st, L;
VB v;
stack<int> stk;
int n, m, nr;

void ReadGraph();
void Df(int x);
void WriteComponents();

int main()
{
    ReadGraph();
    Df(1);
    WriteComponents();

    fin.close();
    fout.close();
    return 0;
}

void WriteComponents()
{
    int cnt;
    fout << nr << '\n';
    for (int i = 1; i <= nr; ++i )
    {
        cnt = comp[i].size();
        for (const auto& j : comp[i] )
            fout << j << ' ';
        fout << t[comp[i][cnt - 1]] << '\n';
    }
}

void Df(int x)
{
    v[x] = true;
    niv[x] = niv[t[x]] + 1;
    for (const auto& y : G[x])
    {
        if ( !v[y] )
        {
            t[y] = x;
            f[x].push_back(y);
            stk.push(y);
            Df(y);
            if ( L[y] >= niv[x] )
            {
                ++nr;
                while ( stk.top() != y )
                {
                    comp[nr].push_back(stk.top());
                    stk.pop();
                }
                comp[nr].push_back(stk.top());
                stk.pop();
            }
        }
    }
    int mi = Inf;
    for (const auto& y : f[x] )
        mi = min(mi, L[y]);
    for (const auto& y : G[x] )
        mi = min(mi, niv[y]);

    L[x] = mi;
}

void ReadGraph()
{
    fin >> n >> m;

    G = f = comp = VVI(n + 1);
    niv = t = st = L = VI(n + 1);
    v = VB(n + 1);

    int x, y;
    while (m--)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}