Cod sursa(job #1208490)

Utilizator 2dorTudor Ciurca 2dor Data 15 iulie 2014 21:21:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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;
stack<int> S;
vector<int> G[MAXN], actual_component;
vector< vector<int> > Components;
int ind = 0, indx[MAXN], N, M, level[MAXN];
bool in_stack[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 father) {
    indx[father] = level[father] = ind++;
    S.push(father); in_stack[father] = true;
    vector<int>::iterator it;
    for (it = G[father].begin(); it != G[father].end(); ++it) {
        if (indx[*it] == -1) {
            Tarjan(*it);
            level[father] = min(level[father], level[*it]);
        }else if (in_stack[*it]) {
            level[father] = min(level[father], level[*it]);
        }
    }
    if (indx[father] == level[father]) {
        actual_component.clear();
        int naux;
        do {
            naux = S.top();
            S.pop(); in_stack[naux] = false;
            actual_component.push_back(naux);
        }while (father != naux);
        Components.push_back( actual_component );
    }
}

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