Cod sursa(job #2118099)

Utilizator DawlauAndrei Blahovici Dawlau Data 30 ianuarie 2018 01:28:45
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 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< vector<int> > BC;

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;
    vector<int> currentBC;

    do{
        firstNodeFromStack = Stack.top().first;
        secondNodeFromStack = Stack.top().second;
        Stack.pop();
        currentBC.push_back(firstNodeFromStack);
        currentBC.push_back(secondNodeFromStack);

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

    BC.push_back(currentBC);
}

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(){

    vector< vector<int> >::iterator it1;
    vector< int >::iterator it2;

    fout << BC.size() << '\n';

    for(it1 = BC.begin(); it1 != BC.end(); ++it1){

        sort((*it1).begin(), (*it1).end());
        (*it1).erase(unique((*it1).begin(), (*it1).end()), (*it1).end());

        for(it2 = (*it1).begin(); it2 != (*it1).end(); ++it2)
            fout << *it2 << ' ';
        fout << '\n';
    }
}

int main(){

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