Cod sursa(job #779616)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 18 august 2012 12:01:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <cassert>
#include <cstdio>

#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

const int N = 100005;

int n, m, c;
bool viz[N];
int d[N], niv[N];
vector <int> vec[N];
vector <int > sol[N];
stack <pair <int, int> > muchii;

void dfs(int nod)
{
    viz[nod] = true;
    d[nod] = niv[nod];

    FORIT(it, vec[nod]) {
        if (!viz[*it]) {
            niv[*it] = niv[nod] + 1;
            muchii.push(make_pair(nod, *it));
            dfs(*it);
            d[nod] = min(d[nod], d[*it]);
            if (d[*it] >= niv[nod]) {
                ++c;
                while (muchii.top() != make_pair(nod, *it)) {
                    sol[c].push_back(muchii.top().first);
                    sol[c].push_back(muchii.top().second);
                    muchii.pop();
                }
                sol[c].push_back(muchii.top().first);
                sol[c].push_back(muchii.top().second);
                muchii.pop();
            }

        } else {
            if (niv[*it] < niv[nod] - 1)
                d[nod] = min(d[nod], niv[*it]);
        }
    }
}

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

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

    dfs(1);
    
    printf("%d\n", c);
    for (int i = 1; i <= c; ++i) {
        sort(sol[i].begin(), sol[i].end());
        vector <int>::iterator it = unique(sol[i].begin(), sol[i].end());
        sol[i].resize(it - sol[i].begin());
        FORIT(it, sol[i])
            printf("%d ", *it);
        printf("\n");
    }
}