Cod sursa(job #972825)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 12 iulie 2013 18:39:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <set>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int MAXN = 100005;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
vector<int> Dfn(MAXN, -1), Low(MAXN);
stack< pair<int, int> > Stack;
vector< set<int> > BConx;
int n, m;

inline void Get_min(int &a, int b)
{
    if(a > b)
        a = b;
}

inline void ReadData(){
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

inline void Get_Biconex(const int x, const int y){
    set<int> ActBconx;
    int X, Y;
    do{
        X = Stack.top().first;
        Y = Stack.top().second;
        Stack.pop();
        ActBconx.insert(X);
        ActBconx.insert(Y);
    }while(X != x || Y != y);
    BConx.push_back(ActBconx);
}

inline void DFs(int Node, int Father, int actLevel){
    Dfn[Node] = Low[Node] = actLevel;
    for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
        if(*it != Father){
            if(Dfn[*it] == -1){
                Stack.push(make_pair(Node, *it));
                DFs(*it, Node, actLevel + 1);
                Get_min(Low[Node], Low[*it]);
                if(Low[*it] >= Dfn[Node])
                    Get_Biconex(Node, *it);
            }
            else Get_min(Low[Node], Dfn[*it]);
        }
}

inline void WriteData(){
    cout << BConx.size() << "\n";
    for(vector< set<int> > :: iterator it = BConx.begin(), fin = BConx.end(); it != fin ; ++ it){
        for(set<int> :: iterator i = it->begin(), j = it->end() ; i != j ; ++ i)
            cout << *i << " ";
        cout << "\n";
    }
}
int main(){
    ReadData();
    DFs(1, 0, 0);
    WriteData();
    cin.close();
    cout.close();
    return 0;
}