Cod sursa(job #1451480)

Utilizator flore77Simion Florentin flore77 Data 17 iunie 2015 11:10:09
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

#define NMAX 100100
#define INF 999999999
#define UNDEFINED 0

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

vector<int> graph[NMAX];
vector<vector<int> > solution;
stack<int> s;
int idx[NMAX]; // timpul de descoperire
int lowlink[NMAX]; // timpul de descoperire al celui mai indepartat stramos (back edges)
bool isInStack[NMAX];
int nodes, index;

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 dfsTarjan(int start) {
    index++;

    idx[start] = index;
    lowlink[start] = index;

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

    for (unsigned int i = 0; i < graph[start].size(); i++) {
        int neighbour = graph[start].at(i);

        if (idx[neighbour] == UNDEFINED) {
            dfsTarjan(neighbour);
            lowlink[start] = min(lowlink[start], lowlink[neighbour]);
        }
        else if (idx[neighbour] != UNDEFINED) {
            lowlink[start] = min(lowlink[start], idx[neighbour]);
        }
    }

    if (lowlink[start] == idx[start]) {
        vector<int> sol;

        while (s.top() != start) {
            sol.push_back(s.top());
            isInStack[s.top()] = false;
            s.pop();
        }
        sol.push_back(s.top());
        isInStack[s.top()] = false;
        s.pop();

        solution.push_back(sol);
    }
}


void Tarjan() {
    index = 0;

    for (int i = 0; i < nodes; i++) {
        if (idx[i] == UNDEFINED) {
            dfsTarjan(i);
        }
    }

    printSolution();
}

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

    in >> nodes >> edges;

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

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

    Tarjan();

    return 0;
}