Cod sursa(job #591066)

Utilizator vladbagrinVlad Bagrin vladbagrin Data 22 mai 2011 00:27:36
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

char** g;
int n;
char *id, *idl;
int d = 0;
stack<int> s;
ostringstream ss("");
int numar = 0;

void tarjan(int u) {
    id[u] = idl[u] = d++;
    s.push(u);

    for (int i = 0; i < n; i++) {
        if (g[u][i] == 1) {
            if (id[i] == -1) {
                tarjan(i);
                if (idl[u] > idl[i]) {
                    idl[u] = idl[i];
                }
            } else if (idl[u] > id[i]) {
                idl[u] = id[i];
            }
        }
    }
    if (id[u] == idl[u]) {
        numar++;
        int v;
        do {
            v = s.top();
            s.pop();
            ss << (int) v + 1 << " ";
        }
        while (v != u);
        ss << endl;
    }
}

int main() {
    ifstream in("ctc.in", ifstream::in);

    in >> n;
    g = new char*[n];
    id = new char[n];
    idl = new char[n];
    
    for (int i = 0; i < n; i++) {
        id[i] = -1;
        idl[i] = -1;
        g[i] = new char[n];
        for (int j = 0; j < n; j++) {
            g[i][j] = 0;
        }
    }
    int m;
    in >> m;

    while (m--) {
        int u, v;
        in >> u;
        in >> v;

        u--;
        v--;

        g[u][v] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (id[i] == -1) {
            tarjan(i);
        }
    }

    delete [] id;
    delete [] idl;
    for (int i = 0; i < n; i++) {
        delete [] g[i];
    }
    delete [] g;

    in.close();

    ofstream out("ctc.out", ofstream::out);
    out << numar << endl << ss.str();
    out.flush();
    out.close();
}