Cod sursa(job #1538390)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 noiembrie 2015 22:29:56
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 1;

vector<int> G[MAX_N];
vector<int> BC[MAX_N];
stack< pair<int,int> > ST;

int lowLink[MAX_N], dfn[MAX_N];

int N, M;
int nrBC;

void biconex(int node, int son)
{
    pair<int,int> p;
    nrBC++;

    do
    {
        p = ST.top();
        ST.pop();

        BC[ nrBC ].emplace_back(p.first);
        BC[ nrBC ].emplace_back(p.second);

    } while (p.first != node || p.second != son);
}

void dfs(int node, int nr)
{
    lowLink[node] = dfn[node] = nr;

    for (int son : G[node])
    {
        if (dfn[son] == 0)
        {
            ST.push({node, son});
            dfs(son, nr + 1);

            lowLink[node] = min(lowLink[node], lowLink[son]);

            if (lowLink[node] >= dfn[node])
            {
                biconex(node, son);
            }
        }
        else
        {
            lowLink[node] = min(lowLink[node], dfn[son]);
        }
    }
}


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

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

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

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

    dfs(1, 1);

    printf("%d\n", nrBC);

    for (int i = 1; i <= nrBC; ++i)
    {
        sort(BC[i].begin(), BC[i].end());
        BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());

        for (int x : BC[i])
            printf("%d ", x);

        puts("");
    }

    return 0;
}