Cod sursa(job #536143)

Utilizator feelshiftFeelshift feelshift Data 18 februarie 2011 12:25:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

#define maxSize 100001

int nodes,count,stronglyConnectedComponents;
bool inStack[maxSize];
int indexx[maxSize];
int lowLink[maxSize];
vector<int> graph[maxSize];
list< list<int> > solution;
stack<int> myStack;

void read();
void tarjan(int currentNode);
void write();

int main() {
    read();

    for(int i=1;i<=nodes;i++)
        if(!indexx[i])
            tarjan(i);

    write();

    return (0);
}

void read() {
    ifstream in("ctc.in");
    int edges,from,to;

    in >> nodes >> edges;
    for(int i=1;i<=edges;i++) {
        in >> from >> to;

        graph[from].push_back(to);
    }

    in.close();
}

void tarjan(int currentNode) {
    indexx[currentNode] = ++count;
    lowLink[currentNode] = count;

    myStack.push(currentNode);
    inStack[currentNode] = true;

    vector<int>::iterator neighbour,end;
    end = graph[currentNode].end();

    for(neighbour=graph[currentNode].begin();neighbour!=end;++neighbour)
        if(!indexx[*neighbour]) {
            tarjan(*neighbour);
            lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);
        }
        else
            if(inStack[*neighbour])
                lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);

    if(lowLink[currentNode] == indexx[currentNode]) {
        int node = 0;
        list<int> currentSolution;

        while(node != currentNode) {
            node = myStack.top();
            myStack.pop();

            inStack[node] = false;

            currentSolution.push_back(node);
        }

        solution.push_back(currentSolution);
        stronglyConnectedComponents++;
    }
}

void write() {
    ofstream out("ctc.out");
    list< list<int> >::iterator first,firstEnd;
    list<int>::iterator second,secondEnd;

    out << stronglyConnectedComponents << "\n";

    firstEnd = solution.end();
    for(first=solution.begin();first!=firstEnd;++first) {
        secondEnd = first->end();

        for(second=first->begin();second!=secondEnd;++second)
            out << *second << " ";
        out << "\n";
    }

    out.close();
}