Cod sursa(job #1690010)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 14 aprilie 2016 18:04:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 10;

int n , m , i , nrc;
bool used[nmax];

int low[nmax] , lvl[nmax];
vector < int > g[nmax] , ans[nmax];

stack < pair < int , int > > s;

void runBC(pair < int , int > edge)
{
    nrc++;
    while (true)
    {
        pair < int , int > act = s.top();
        s.pop();

        ans[nrc].push_back(act.second);
        if (act == edge) break;
    }

    ans[nrc].push_back(edge.first);
}

void dfs(int node)
{
    used[node] = 1;
    low[node] = lvl[node];

    for (auto &it : g[node])
    {
        if (used[it])
        {
            low[node] = min(low[node] , lvl[it]);
            continue;
        }

        lvl[it] = lvl[node] + 1;

        s.push({node,it});
        dfs(it);

        low[node] = min(low[node] , low[it]);
        if (lvl[node] <= low[it]) runBC({node,it});
    }
}

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

    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; ++i)
    {
        int x , y;
        scanf("%d %d", &x, &y);

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

    lvl[1] = 1; dfs(1);

    printf("%d\n", nrc);
    for (i = 1; i <= nrc; ++i, printf("\n"))
        for (auto &it : ans[i])
            printf("%d ", it);

    return 0;
}