Cod sursa(job #2118246)

Utilizator DawlauAndrei Blahovici Dawlau Data 30 ianuarie 2018 13:35:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
#include<cstdio>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
const int NMAX = 100005, BUFFERSIZE = 40000;

char readBuffer[BUFFERSIZE];
int readCursor = BUFFERSIZE - 1;

inline void read(int &number){

    while(!(readBuffer[readCursor] >= '0' and readBuffer[readCursor] <= '9'))
        if(++readCursor == BUFFERSIZE){

            readCursor = 0;
            fread(readBuffer, 1, BUFFERSIZE, stdin);
        }

    number = 0;
    while(readBuffer[readCursor] >= '0' and readBuffer[readCursor] <= '9'){

        number = number * 10 + readBuffer[readCursor] - '0';
        if(++readCursor == BUFFERSIZE){

            readCursor = 0;
            fread(readBuffer, 1, BUFFERSIZE, stdin);
        }
    }
}

char printBuffer[BUFFERSIZE];
int printCursor;

inline void printChar(const char &character){

    printBuffer[printCursor++] = character;
    if(printCursor == BUFFERSIZE){

        fwrite(printBuffer, 1, BUFFERSIZE, stdout);
        printCursor = 0;
    }
}

inline void printInteger(int number){

    char digits[10];
    int numberLength = 0;

    while(number){

        digits[++numberLength] = number % 10 + '0';
        number /= 10;

    }

    while(numberLength){
        printChar(digits[numberLength]);
        --numberLength;
    }
}

list<int> graph[NMAX], SCC[NMAX];
stack<int> Stack;
bitset<NMAX> inStack;

int nodesCount, edgesCount, traversalMoment, SCCCount;
int link[NMAX], lowLink[NMAX];

inline void read_data(){

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

    read(nodesCount); read(edgesCount);

    int from, to;
    while(edgesCount--){

        read(from); read(to);
        graph[from].push_back(to);
    }
}

inline void getNewSCC(int node){

    ++SCCCount;

    int topOfTheStack;
    do{

        topOfTheStack = Stack.top();
        inStack[topOfTheStack] = false;
        Stack.pop();
        SCC[SCCCount].push_back(topOfTheStack);

    }while(node != topOfTheStack);

}

void getSCC(int node){

    link[node] = lowLink[node] = ++traversalMoment;
    Stack.push(node);
    inStack[node] = true;

    list<int>::iterator nextNode;
    for(nextNode = graph[node].begin(); nextNode != graph[node].end(); ++nextNode)
        if(link[*nextNode] == 0){

            getSCC(*nextNode);
            lowLink[node] = min(lowLink[node], lowLink[*nextNode]);
        }
        else if(inStack[*nextNode])
            lowLink[node] = min(lowLink[node], lowLink[*nextNode]);

    if(link[node] == lowLink[node])
        getNewSCC(node);
}

inline void solve(){

    int node;
    for(node = 1; node <= nodesCount; ++node)
        if(link[node] == 0)
            getSCC(node);
}

inline void printSCC(){

    printInteger(SCCCount);
    printChar('\n');

    int index;
    list<int>::iterator node;
    for(index = 1; index <= SCCCount; ++index){

        for(node = SCC[index].begin(); node != SCC[index].end(); ++node)
            printInteger(*node), printChar(' ');
        printChar('\n');
    }
    fwrite(printBuffer, 1, BUFFERSIZE, stdout);
}
int main(){

    read_data();
    solve();
    printSCC();
}