Cod sursa(job #1157232)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 28 martie 2014 12:39:19
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int n, nd;
vector<int> vec[100010];
stack<int> s;
vector<vector<int> > sol;

int viz[100010];
int dfn[100010];
int low[100010];

void citire()
{
    int n, m , x, y;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m ; i++)
    {
        scanf("%d%d", &x, &y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
}

void adaug(int x)
{
    vector<int> newsol;
    newsol.clear();
    while(!s.empty() && s.top() != x)
    {
        newsol.push_back(s.top());
        s.pop();
    }
    newsol.push_back(x);
    sol.push_back(newsol);
}

void solve(int x = 1, int tata = 0)
{
    int crt = nd;
    dfn[x] = crt;
    low[x] = crt;
    nd++;
    viz[x] = 1;
    int fibuni = 0;

    for(int i = 0; i < vec[x].size(); i++)
        if(!viz[vec[x][i]])
        {
            s.push(vec[x][i]);
            fibuni++;
            solve(vec[x][i], x);
            low[x] = min(low[x], low[vec[x][i]]);
            if(low[x] >= dfn[x])
                adaug(x);
        }
        else if(vec[x][i]!=tata)
        {
            low[x] = min(low[x], low[vec[x][i]]);
        }
}

void afisare()
{
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); i++)
    {
        for(int j = 0; j < sol[i].size(); j++)
            printf("%d ", sol[i][j]);
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    citire();
    solve();
    afisare();
    return 0;
}