Cod sursa(job #1185548)

Utilizator andreiiiiPopa Andrei andreiiii Data 15 mai 2014 22:52:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int Nmax = 100005;

bitset<Nmax> v;
vector<int> G[Nmax];
vector<vector<int>> Bcomps;
stack<int> St;

int Lvl[Nmax], LowLvl[Nmax];
int N;

void AddBcomp(const int fnode, const int node)
{
    vector<int> bcomp;

    while (St.top() != node)
    {
        bcomp.push_back(St.top());
        St.pop();
    }
    bcomp.push_back(node);
    St.pop();

    bcomp.push_back(fnode);

    Bcomps.push_back(bcomp);
}

void Dfs(const int node, const int lvl)
{
    Lvl[node] = lvl;
    LowLvl[node] = lvl;

    v[node] = 1;
    St.push(node);

    for (auto p: G[node])
    {
        if (v[p])
            LowLvl[node] = min(LowLvl[node], Lvl[p]);
        else
        {
            Dfs(p, lvl + 1);

            LowLvl[node] = min(LowLvl[node], LowLvl[p]);

            if (LowLvl[p] >= lvl) AddBcomp(node, p);
        }
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    int M;
    scanf("%d%d", &N, &M);

    while (M--)
    {
        int x, y;
        scanf("%d%d", &x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= N; i++)
        if (!v[i])
            Dfs(i, 0);

    printf("%u\n", Bcomps.size());
    for (auto p: Bcomps)
    {
        for (auto l: p)
            printf("%d ", l);

        printf("\n");
    }
}