Cod sursa(job #1208445)

Utilizator 2dorTudor Ciurca 2dor Data 15 iulie 2014 19:16:12
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

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

const int MAXN = 100005;
vector<int> G[MAXN], actual_comp;
vector< vector<int> > Components;
stack<int> S;
bool in_stack[MAXN];
int N, M, ind, index[MAXN], lowlink[MAXN];

void Read() {
    fin >> N >> M;
    int a, b;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b;
        G[a].push_back(b);
    }
}

void tarjan(int node) {
    index[node] = lowlink[node] = ind++;
    S.push(node);
    in_stack[node] = true;
    vector<int>::iterator it;
    for (it = G[node].begin(); it != G[node].end(); ++it) {
        if (index[*it] == -1) {
            tarjan(*it);
            lowlink[node] = min(lowlink[node], lowlink[*it]);
        }else if (in_stack[*it]) {
            lowlink[node] = min(lowlink[node], lowlink[*it]);
        }
    }
    if (index[node] == lowlink[node]) {//we've found a stongly connected component
        actual_comp.clear();
        int aux;
        do {
            aux = S.top();
            actual_comp.push_back(aux);
            S.pop();
            in_stack[node] = 0;
        }while (node != aux);
        Components.push_back(actual_comp);
    }
}

void Solve() {
    memset(index, -1, sizeof(index));
    for (int i = 1; i <= N; ++i) {
        if (index[i] == -1)
            tarjan(i);
    }
}

void Write() {
    fout << Components.size() << "\n";
    for (size_t i = 0; i < Components.size(); ++ i) {
        for (size_t j = 0; j < Components[i].size(); ++ j)
            fout << Components[i][j] << " ";
        fout << "\n";
    }
}

int main() {
    Read();
    Solve();
    Write();
    fin.close();
    fout.close();
    return 0;
}