Cod sursa(job #1540598)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 2 decembrie 2015 22:36:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <stack>
#include <vector>

using namespace std;

const int DIM = 131072;

int nrNodes, nrEdges, nrComponents, node1, node2, Lower[DIM], Level[DIM];
stack <int> Stack; vector <int> Components[DIM], Edges[DIM]; bitset <DIM> Marked;

void DFS (int node, int level, int father) {

    Marked[node] = 1;
    Level[node] = level;
    Lower[node] = level;

    Stack.push(node);

    vector <int> :: iterator it;
    for (it = Edges[node].begin(); it != Edges[node].end(); it ++) {
        int nextNode = *it;

        if (nextNode == father)
            continue;

        if (!Marked[nextNode]) {

            DFS (nextNode, level + 1, node);
            Lower[node] = min (Lower[node], Lower[nextNode]);

            if (Level[node] <= Lower[nextNode]) {
                nrComponents ++;
                int topNode;

                do {

                    topNode = Stack.top();
                    Components[nrComponents].push_back(topNode);
                    Stack.pop();

                } while (topNode != nextNode);

                Components[nrComponents].push_back(node);
            }

        } else
            Lower[node] = min (Lower[node], Level[nextNode]);
    }

    return;
}

int main () {

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

    scanf ("%d %d", &nrNodes, &nrEdges);
    for (int i = 1; i <= nrEdges; i ++) {
        scanf ("%d %d", &node1, &node2);

        Edges[node1].push_back(node2);
        Edges[node2].push_back(node1);
    }

    for (int i = 1; i <= nrNodes; i ++)
        if (!Marked[i]) DFS (i, 1, 0);

    printf ("%d\n", nrComponents);
    for (int i = 1; i <= nrComponents; i ++) {

        vector <int> :: iterator it;
        for (it = Components[i].begin(); it != Components[i].end(); it ++) {
            int node = *it;

            printf ("%d ", node);
        }
        printf ("\n");
    }

    return 0;
}