Cod sursa(job #591068)

Utilizator vladbagrinVlad Bagrin vladbagrin Data 22 mai 2011 00:39:40
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

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

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

    int c;
    for (unsigned int i = 0; i < g[u].size(); i++) {
        c = g[u][i];
        if (id[c] == -1) {
            tarjan(c);
            if (idl[u] > idl[c]) {
                idl[u] = idl[c];
            }
        } else if (in_s[c] == 1) {
            if (idl[u] > id[c]) {
                idl[u] = id[c];
            }
        }
    }

    if (id[u] == idl[u]) {
        numar++;
        int v;
        do {
            v = s.top();
            s.pop();
            in_s[v] = 0;
            ss << (int) v + 1 << " ";
        }
        while (v != u);
        ss << endl;
    }
}

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

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

    int u, v;
    for (int i = 0; i < m; i++) {
        in >> u;
        in >> v;

        g[u - 1].push_back(v - 1);
    }

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

    delete [] id;
    delete [] idl;
    delete [] in_s;

    in.close();

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