Cod sursa(job #1131390)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 28 februarie 2014 19:53:07
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
//Voi scoate Santa de 100 de puncte $$$

#include <stdio.h>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <map>

using namespace std;

//input
int N, M, source, sink, mlc;
vector <int> G[50000];

//componente biconexe
int low[50000], ord[50000], vis_biconex[50000];
pair <int, int> st[50000];
vector <int> cbc[50500];
int timp = 0, cntBiconex = 0, cntSt = 0;

void read() {
    //freopen("santa.in", "r", stdin);
    //freopen("santa.out", "w", stdout);

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

    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        int xx, yy;
        scanf("%d%d", &xx, &yy);
        G[xx].push_back(yy);
        G[yy].push_back(xx);
    }
    //scanf("%d%d%d", &source, &sink, &mlc);
}

void load_component(int xx, int yy) {
    ++cntBiconex;
    map <int, bool> MP;
    while (cntSt > 0) {
        int curx = st[cntSt].first;
        int cury = st[cntSt].second;
        if (MP[curx] == 0) {
            MP[curx] = 1;
            cbc[cntBiconex].push_back(curx);
        }
        if (MP[cury] == 0) {
            MP[cury] = 1;
            cbc[cntBiconex].push_back(cury);
        }
        --cntSt;
        if (curx == xx && cury == yy)
            break;
    }
}

void dfs_biconex(int nod) {
    vector <int> :: iterator it;
    vis_biconex[nod] = 1;
    ord[nod] = low[nod] = ++timp;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
        if (!vis_biconex[*it]) {
            st[++cntSt].first = nod; st[cntSt].second = *it;
            dfs_biconex(*it);
            if (low[*it] >= ord[nod])
                load_component(nod, *it);
            if (low[*it] < low[nod])
                low[nod] = low[*it];
        } else if (ord[*it] < low[nod])
            low[nod] = ord[*it];
}

int main() {
    read();
    dfs_biconex(1);

    printf("%d\n", cntBiconex);
    for (int i = 1; i <= cntBiconex; ++i, printf("\n"))
        for (vector <int> :: iterator it = cbc[i].begin(); it != cbc[i].end(); ++it)
            printf("%d ", *it);

    return 0;
}