Cod sursa(job #1453574)

Utilizator alex.bullzAlexandru Lilian alex.bullz Data 23 iunie 2015 21:10:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

struct Node {
    int discoveryTime;
    int lowLink;
    std::vector<int> neighbors;
    bool inStack;

    Node() {
        discoveryTime = -1;
        lowLink = -1;
        inStack = false;
    }
};

int g_time = 1, g_counter;
std::stack<int> s;
std::vector<std::vector<int> > components;

void tarjan (int index, std::vector<Node>& graph) {
    s.push (index);
    graph[index].inStack = true;
    graph[index].discoveryTime = g_time;
    graph[index].lowLink = g_time;
    g_time++;

    auto neighbors = graph[index].neighbors;

    for (int i = 0; i < neighbors.size(); ++i) {
        if (graph[neighbors[i]].discoveryTime == -1) {
            tarjan (neighbors[i], graph);
            graph[index].lowLink = std::min (graph[index].lowLink, graph[neighbors[i]].lowLink);
        } 
    }

    if (graph[index].lowLink == graph[index].discoveryTime) {
        std::vector<int> ctc;
        int aux = -1;
        g_counter++;
        do {
            aux = s.top();
            ctc.push_back (aux);
            s.pop();
            graph[aux].inStack = false;
        } while (aux != index);
        components.push_back (ctc);
    }
}

int main() {
    std::ifstream fin ("ctc.in");
    std::ofstream fout ("ctc.out");
    int n, m;

    fin >> n >> m;

    std::vector<Node> graph (n + 1);

    for (int i = 0; i < m; ++i) {
        int source, dest;
        fin >> source >> dest;
        graph[source].neighbors.push_back (dest);
    }

    for (int i = 1; i <= n; ++i) {
        if (graph[i].discoveryTime == -1) {
            tarjan (i, graph);
        }
    }

    fout << g_counter << "\n";
//    std::cout << "nr comp: " <<  g_counter << "\n";
//    std::cout << "prima: " << components[0].size() << "\na doua: " << components[1].size() << "\n";
    for (int i = 0; i < g_counter; ++i) {
//        std::cout << "intra i\n";
        for (int j = 0; j < components[i].size(); ++j) {
//            std::cout << "intra j\n";
            fout << components[i][j] << " ";
//            std::cout << components[i][j] << " ";
        }
        fout << "\n";
    }

    return 0;
}