Cod sursa(job #1451436)

Utilizator flore77Simion Florentin flore77 Data 17 iunie 2015 00:50:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

#define NMAX 100100

ifstream in("ctc.in");
ofstream out("ctc.out");

vector<int> originalGraph[NMAX];
vector<int> reverseGraph[NMAX];
stack<int> finalDecOrderNodes; // vector in care vor fi retinute nodurile in ordinea descrescatoare a timpilor de finalizare
vector<vector<int> > solution;
bool visited[NMAX];
int nodes;


inline void initVisited() {
    for (int i = 0; i < nodes; i++)
        visited[i] = false;
}

inline void printSolution() {
    out << solution.size() << "\n";

    for (unsigned i = 0; i < solution.size(); i++) {
        for (unsigned j = 0; j < solution.at(i).size(); j++) {
            out << solution.at(i).at(j) + 1 << " ";
        }
        out << "\n";
    }
}

void dfsOriginal(int start) {
    stack<int> s;

    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int current = s.top();

        int neighbour = -1;

        for (unsigned int i = 0; i < originalGraph[current].size(); i++) {
            if (!visited[originalGraph[current].at(i)]) {
                neighbour = originalGraph[current].at(i);
                break;
            }
        }

        if (neighbour != - 1) {
            visited[neighbour] = true;
            s.push(neighbour);
        }
        else {
            s.pop();
            finalDecOrderNodes.push(current);
        }
    }
}

void dfsReverse(int start) {
    stack<int> s;
    vector<int> sol;

    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int current = s.top();

        int neighbour = -1;

        for (unsigned int i = 0; i < reverseGraph[current].size(); i++) {
            if (!visited[reverseGraph[current].at(i)]) {
                neighbour = reverseGraph[current].at(i);
                break;
            }
        }

        if (neighbour != - 1) {
            visited[neighbour] = true;
            s.push(neighbour);
        }
        else {
            s.pop();
            sol.push_back(current);
        }
    }

    solution.push_back(sol);
}

void Kosaraju() {
    initVisited();

    // sortare topologica
    for (int i = 0; i < nodes; i++) {
        if (!visited[i])
            dfsOriginal(i);
    }

    initVisited();

    while(!finalDecOrderNodes.empty()) {
        int current = finalDecOrderNodes.top();
        finalDecOrderNodes.pop();

        if (visited[current])
            continue;

        dfsReverse(current);
    }

    printSolution();
}

int main() {
    int edges, x, y;

    in >> nodes >> edges;

    for (int i = 0; i < edges; i++) {
        in >> x >> y;

        originalGraph[x - 1].push_back(y - 1);
        reverseGraph[y - 1].push_back(x - 1);
    }

    Kosaraju();

    return 0;
}