Cod sursa(job #1708665)

Utilizator UPB_Darius_Rares_SilviuPeace my pants UPB_Darius_Rares_Silviu Data 27 mai 2016 19:15:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 100009
#define x first
#define y second
using namespace std;
typedef pair<int, int> edge;

int N, M, T[ NMAX ], order, found[ NMAX ], low[ NMAX ];
vector< int > G[ NMAX ];
vector< vector<int> > bcc;
stack<edge> st;

template<class T>
void makeUnique(vector<T> &v){
  sort(v.begin(), v.end());
  v.erase( unique( v.begin(), v.end() ), v.end());
}

void getBCC(edge e) {
    vector<int> v;
    edge aux;
    do{
      aux = st.top();
      v.push_back( aux.x );
      v.push_back( aux.y );
      st.pop();
    }while(aux != e);

    makeUnique( v );
    bcc.push_back( v );
}


void DFS(int node) {
    found[ node ] = low[ node ] = ++order;
    int children;

    for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        if (!T[ *it ]) {
            ++children;
            T[ *it ] = node;
            st.push( edge(node, *it) );
            DFS( *it );

            low[ node ] = min(low[ node ], low[ *it ]);

            if (low[ *it ] >= found[ node ]) {
                getBCC( edge(node, *it) );
            }
        } else {
            low[ node ] = min(low[ node ], found[ *it ]);
        }
    }
}

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

    scanf("%d%d", &N, &M);
    while (M--) {
        int x, y;
        scanf("%d%d", &x, &y);
        G[ x ].push_back ( y );
        G[ y ].push_back( x );
    }

    for (int i = 1; i <= N; ++i) {
        if (!T[ i ]) {
            T[ i ] = i;
            DFS( i );
        }
    }

    printf("%d\n", bcc.size());
    for (int i = 0; i < (int) bcc.size(); ++i) {
        for (vector<int>::iterator it = bcc[ i ].begin(); it != bcc[ i ].end(); ++it) {
            printf("%d ", *it);
        }
        printf("\n");
    }


    return 0;
}