Cod sursa(job #1420868)

Utilizator avram_florinavram florin constantin avram_florin Data 19 aprilie 2015 02:56:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

vector<vector<int>> graph, ctc;
vector<int> index, lowlink;
vector<bool> in_stack;
stack<int> st;
int N, M;
int ind = 0;

const char  in_file[] = "ctc.in";
const char out_file[] = "ctc.out";

void read_file()
{
    ifstream fin(in_file);
    int x, y;

    fin >> N >> M;
    graph.resize(N+1);
    index.resize(N+1);
    lowlink.resize(N+1);
    in_stack.resize(N+1);
    index.assign(N+1, -1);

    for (int i = 0; i < M; ++i) {
        fin >> x >> y;
        graph[x].push_back(y);
    }
    fin.close();
}

inline int minim(const int &a, const int &b) {
    return a < b ? a : b;
}

void tarjan(int node)
{
    index[node] = ind;
    lowlink[node] = ind;
    ind++;

    st.push(node);
    in_stack[node] = true;

    for (auto it = graph[node].begin(); it < graph[node].end(); ++it) {
        if (index[*it] == -1) {
            tarjan(*it);
            lowlink[node] = minim(lowlink[node], lowlink[*it]);
        }
        else if (in_stack[*it]) {
                lowlink[node] = minim(lowlink[node], lowlink[*it]);
            }
    }

    if (index[node] == lowlink[node]) {
        vector<int> c;
        int n;

        do {
            n = st.top(); st.pop();
            in_stack[n] = false;
            c.push_back(n);
        } while (node != n);
        ctc.push_back(c);
    }
}

void print_result()
{
    ofstream fout(out_file);
    fout << ctc.size() << '\n';

    for (auto it = ctc.begin(); it < ctc.end(); ++it) {
        for (auto jt = it->begin(); jt < it->end(); ++jt) 
            fout << *jt << ' ';
        fout << '\n';
    }
    fout.close();
}

int main() {
    read_file();
    for (int i = 1; i < N; ++i)
        if (index[i] == -1)
            tarjan(i);
    print_result();
}