Cod sursa(job #1667767)

Utilizator ZenusTudor Costin Razvan Zenus Data 29 martie 2016 10:53:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 100009;

vector < int > all[nmax] , g[nmax];
pair < int , int > is[nmax];
int lvl[nmax] , lmin[nmax] , mark[nmax];
int n , m , i , a , b , j , S , top;

void runBC(pair < int , int > edge)
{
    vector < int > bc;

    while (true)
    {
        pair < int , int > act = is[top--];
        bc.push_back(act.second);
        if (act == edge)
        {
            bc.push_back(act.first);
            break;
        }
    }

    all[++S] = bc;
}

void dfs(int act , int up)
{
    lvl[act] = lvl[up] + 1;
    lmin[act] = lvl[act];
    mark[act] = 1;

    for (int i = 0 ; i < g[act].size() ; ++i)
    {
        int x = g[act][i];
        if (x == up) continue;

        if (!mark[x])
        {
            is[++top] = make_pair(act , x);
            dfs(x , act);
            lmin[act] = min(lmin[act] , lmin[x]);

            if (lvl[act] <= lmin[x]) runBC({act , x});
        }
        else lmin[act] = min(lmin[act] , lvl[x]);
    }
}

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

scanf("%d" , &n);
scanf("%d" , &m);

for (i = 1 ; i <= m ; ++i)
{
    scanf("%d" , &a);
    scanf("%d" , &b);

    g[a].push_back(b);
    g[b].push_back(a);
}

dfs(1 , 0);

printf("%d\n" , S);
for (i = 1 ; i <= S ; ++i , printf("\n"))
for (j = 0 ; j < all[i].size() ; ++j)
printf("%d " , all[i][j]);

return 0;
}