Cod sursa(job #1129174)

Utilizator 2dorTudor Ciurca 2dor Data 27 februarie 2014 20:33:36
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

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

const int MAXN = 100005;

int N, M, NrSol;
bool in_stack[MAXN];
int level[MAXN];//nivelul minim accesibil
int index[MAXN];//nivelul nodului
int indexx = 1;
vector<int> G[MAXN];
vector<int> Sol[MAXN];
stack<int> stiva;

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) {
    cerr << father << '\n';
    level[father] = index[father] = indexx++;
    stiva.push(father);
    in_stack[father] = true;
    vector<int>::iterator it;
    for (it = G[father].begin(); it != G[father].end(); ++it) {
        if (index[*it] == -1) {
            tarjan(*it);
            level[father] = min(level[father], level[*it]);
        }else if (in_stack[*it])
            level[father] = min(level[father], level[*it]);
    }
    if (index[father] == level[father]) {
        int node;
        do {
            node = stiva.top();
            Sol[NrSol].push_back(node);
            stiva.pop();
            in_stack[node] = false;
        }while (father != node);
        ++NrSol;
    }
}

void Write() {
    fout << NrSol << '\n';
    for (int i = 0; i < NrSol; ++i) {
        for (unsigned int j = 0; j < Sol[i].size(); ++j)
            fout << Sol[i][j] << ' ';
        fout << '\n';
    }
}

int main() {
    Read();
    for (int i = 1; i <= N; ++i)
        index[i] = -1;
    cerr << "read\n";
    for (int i = 1; i <= N; ++i)
        if (index[i] == -1)
            tarjan(i);
    cerr << "solved.\n";
    Write();
    fin.close();
    fout.close();
    return 0;
}