Cod sursa(job #1236432)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 1 octombrie 2014 22:15:13
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
#define INF 999999999

using namespace std;

int n, m;
int h[100010], hmin[100010], viz[100010];
vector<int> vec[100010];
vector<vector<int> > sol;
vector<int> s;

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

void adsol(int x)
{
    vector<int> newsol;
    newsol.clear();

    while(s.back() != x)
    {
        newsol.push_back(s.back());
        s.pop_back();
    }
    newsol.push_back(x);
   // s.pop_back();
    sol.push_back(newsol);
}

int solve(int x = 1, int tata = 0)
{
    s.push_back(x);
    viz[x] = 1;
    hmin[x] = h[x] = h[tata] + 1;
    int neviz = 0;

    for(int i = 0; i < vec[x].size(); i++)
    {
        if(!viz[vec[x][i]])
        {
            if(neviz)
                s.push_back(x);
            neviz++;
            solve(vec[x][i], x);
            hmin[x] = min(hmin[x], hmin[vec[x][i]]);
            if(hmin[vec[x][i]] >= h[x])
            {
                adsol(x);
                if(neviz > 1)
                    s.pop_back();
            }
        }
        else if(vec[x][i] != tata)
            hmin[x] = min(hmin[x], h[vec[x][i]]);
    }

}

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

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