Cod sursa(job #1208448)

Utilizator 2dorTudor Ciurca 2dor Data 15 iulie 2014 19:23:41
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 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, indexx[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) {
    indexx[node] = lowlink[node] = ind; ++ind;
    S.push(node);
    in_stack[node] = true;
    vector<int>::iterator it;
    for (it = G[node].begin(); it != G[node].end(); ++it) {
        if (indexx[*it] == -1) {
            tarjan(*it);
            lowlink[node] = min(lowlink[node], lowlink[*it]);
        }else if (in_stack[*it]) {
            lowlink[node] = min(lowlink[node], lowlink[*it]);
        }
    }
    if (indexx[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] = false;
        }while (node != aux);
        Components.push_back(actual_comp);
    }
}

void Solve() {
    for (int i = 1; i <= N; ++i)
        indexx[i] = -1;
    for (int i = 1; i <= N; ++i) {
        if (indexx[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;
}