Cod sursa(job #449005)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 mai 2010 12:19:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>

using namespace std;

#define maxN    100100
#define ROOT    1
#define oo      100100
#define maxM    200100

bitset <maxN> viz, art_point;
vector <int> G[maxN];
set <int> Sol_vec[maxM];
vector < pair <int, int> > stack;

int nivel[maxN], low[maxN], N, M, cate_ramase, Sol, Nr;

void df (int nod, int parinte) {
    int niv_min = oo;

    viz[nod] = 1; nivel[nod] = nivel[parinte] + 1;
    cate_ramase --;
    low[nod] = nivel[nod];

    for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it) {
        if (*it == parinte || (viz[*it] && nivel[*it] > nivel[nod]))
            continue;
        
        if (viz[*it]) {
            low[nod] = min(low[nod], nivel[*it]);
            stack.push_back(make_pair(nod, *it));
        } else {
            stack.push_back(make_pair(nod, *it));
            df(*it, nod);
            niv_min = min(niv_min, low[*it]);
            if (low[*it] >= nivel[nod] && nod != ROOT) {
                art_point[nod] = 1;
    //            fprintf(stderr, "art_point = %d\n", nod);
                ++ Nr;

                for (; stack.back() != make_pair(nod, *it); stack.pop_back()) {
                    Sol_vec[Nr].insert(stack.back().first);
                    Sol_vec[Nr].insert(stack.back().second);
      //              fprintf(stderr, "%d %d\n", stack.back().first, stack.back().second);
                }

                Sol_vec[Nr].insert(stack.back().first);
                Sol_vec[Nr].insert(stack.back().second);
                stack.pop_back();
            }
        }

        if (nod == ROOT && cate_ramase > 0) {
            art_point[ROOT] = 1;
            ++ Nr;
            for (; stack.back() != make_pair(nod, *it); stack.pop_back()) {
                Sol_vec[Nr].insert(stack.back().first);
                Sol_vec[Nr].insert(stack.back().second);
            }
            Sol_vec[Nr].insert(stack.back().first);
            Sol_vec[Nr].insert(stack.back().second);
            stack.pop_back();
        }
    }

    low[nod] = min(low[nod], niv_min);
}

int main () {
    int i, a, b, j;

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

    scanf("%d%d", &N, &M);

    for (i = 1; i <= M; ++ i) {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    cate_ramase = N;
    df(ROOT, 0);

    if (stack.size()) {
        ++ Nr;

        for (; stack.size(); stack.pop_back()) {
            Sol_vec[Nr].insert(stack.back().first);
            Sol_vec[Nr].insert(stack.back().second);
        }
    }
    printf("%d\n", Nr);

    for (i = 1; i <= Nr; ++ i) {
        for (set <int> :: iterator it = Sol_vec[i].begin(); it != Sol_vec[i].end(); ++ it)
            printf("%d ", *it);
        puts("");
    }
}