Cod sursa(job #447683)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 30 aprilie 2010 11:23:53
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 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], Set_biconex[maxN];

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]);        
        } else {
            df(*it, nod);
            niv_min = min(niv_min, low[*it]);
            if (low[*it] >= nivel[nod] && nod != ROOT)
                art_point[nod] = 1;
        }

        if (nod == ROOT && cate_ramase > 0)
            art_point[ROOT] = 1;
    }

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

void df2 (int nod) {
    //fprintf(stderr, "%d ", nod);
    Sol_vec[Nr].insert(nod);
    
    if (art_point[nod] == 1) {
        Set_biconex[nod].insert(Nr);
        return;
    }

    viz[nod] = 1;

    for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it)
        if (! viz[*it])
            df2(*it);
}

bool set_intersect (int i, int j) {
    if (Set_biconex[i].size() > Set_biconex[j].size())
        swap(i, j);

    for (set <int> :: iterator it = Set_biconex[i].begin(); it != Set_biconex[i].end(); ++ it)
        if (Set_biconex[j].find(*it) != Set_biconex[j].end())
            return true;
    return false;
}

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);

    viz.reset();

    for (i = 1; i <= N; ++ i)
        if (! art_point[i] && ! viz[i]) {
            ++ Nr;
            df2(i);
      //      fprintf(stderr, "\n");
        }

    for (i = 1; i <= N; ++ i)
        if (art_point[i] == 1)
            for (vector <int> :: iterator it = G[i].begin(); it != G[i].end(); ++ it)
                if (art_point[*it] && *it > i && ! set_intersect (i, *it)) {
                    ++ Nr;
                    Sol_vec[Nr].insert(i);
                    Sol_vec[Nr].insert(*it);
                }

    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("");
    }
}