Cod sursa(job #2118100)

Utilizator DawlauAndrei Blahovici Dawlau Data 30 ianuarie 2018 01:34:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include<fstream>
#include<list>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100005;

///BC = Biconnected Component

list<int> graph[NMAX];
stack< pair< int , int > > Stack;
vector<int> BC[NMAX];

int nodesCount, edgesCount, BCCount;
int level[NMAX], lowLevel[NMAX];

inline void read_data(){

    fin >> nodesCount >> edgesCount;

    int firstNode, secondNode;
    while(edgesCount--){

        fin >> firstNode >> secondNode;
        graph[firstNode].push_back(secondNode);
        graph[secondNode].push_back(firstNode);
    }
}

inline void cache_newBC(int firstNode, int secondNode){

    int firstNodeFromStack, secondNodeFromStack;
    ++BCCount;

    do{
        firstNodeFromStack = Stack.top().first;
        secondNodeFromStack = Stack.top().second;
        Stack.pop();
        BC[BCCount].push_back(firstNodeFromStack);
        BC[BCCount].push_back(secondNodeFromStack);

    }while(firstNodeFromStack != firstNode and secondNodeFromStack != secondNode);

}

void getBC(int node, int currentLevel){

    level[node] = lowLevel[node] = currentLevel;
    list<int>::iterator it;

    for(it = graph[node].begin(); it != graph[node].end(); ++it)
        if(level[*it] == 0){

            Stack.push({node, *it});
            getBC(*it, currentLevel + 1);

            lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
            if(level[node] <= lowLevel[*it])
                cache_newBC(node, *it);
        }
        else
            lowLevel[node] = min(lowLevel[node], level[*it]);
}

inline void printBC(){

    int index;
    vector< int >::iterator it;

    fout << BCCount << '\n';

    for(index = 1; index <= BCCount; ++index){

        sort(BC[index].begin(), BC[index].end());
        BC[index].erase(unique(BC[index].begin(), BC[index].end()), BC[index].end());

        for(it = BC[index].begin(); it != BC[index].end(); ++it)
            fout << *it << ' ';
        fout << '\n';
    }
}

int main(){

    read_data();
    getBC(1, 1);
    printBC();
}