Cod sursa(job #1921011)

Utilizator EpictetStamatin Cristian Epictet Data 10 martie 2017 11:03:32
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

fstream fin ("biconex.in", ios::in), fout ("biconex.out", ios::out);

int n, m, low[100010], dfn[100010];
vector < int > G[100010];
vector < vector < int > > Sol;
vector < bool > F(100010);
stack < int > S;

inline int Minim(const int &a, const int &b)
{
    if (a < b) return a;
    return b;
}

void Add_Biconex_Component(int pct_art)
{
    Sol.push_back(vector < int > ());
    while (S.top() != pct_art)
    {
        Sol[Sol.size() - 1].push_back(S.top());
        S.pop();
    }
    Sol[Sol.size() - 1].push_back(pct_art);
}

void Biconex(int node, int level)
{
    dfn[node] = low[node] = level;
    F[node] = true;
    S.push(node);
    for (auto it : G[node])
    {
        if (F[it])
        {
            low[node] = Minim(low[node], dfn[it]);
        }
        else
        {
            Biconex(it, level + 1);
            low[node] = Minim(low[node], low[it]);
            if (low[it] >= level) Add_Biconex_Component(node);
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; i ++)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Biconex(1, 0);
    fout << Sol.size() << '\n';
    for (auto it1 : Sol)
    {
        for (auto it2 : it1)
        {
            fout << it2 << ' ';
        }
        fout << '\n';
    }
    fout.close();
    return 0;
}