Cod sursa(job #946226)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 4 mai 2013 02:01:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<vector>
#include<fstream>
#include<stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int N, M;
vector<int> *G, *GT, aux;
vector<char> viz;
stack<int> st;
vector<vector<int>> comp_conexe;

void DF(int nod) {

    viz[nod] = 1;
    for(auto it = G[nod].begin(), it2 = G[nod].end(); it!=it2; ++it)
        if(!viz[*it])
            DF(*it);
    st.push(nod);
}

void DF2(int nod) {

    aux.push_back(nod);
    viz[nod] = -1;
    for(auto it = GT[nod].begin(), it2 = GT[nod].end(); it!=it2; ++it)
        if(viz[*it] != -1)
            DF2(*it);
}

int main() {

    int  i, x, y, nod;

    f >> N >> M;
    G = new vector<int>[N+1];
    GT = new vector<int>[N+1];
    viz.resize(N+1);
    fill(viz.begin(), viz.end(), 0);
    while(M--) {
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(i=1; i<=N; ++i)
        if(!viz[i])
            DF(i);

    while(!st.empty()) {
        nod = st.top();
        st.pop();
        if(viz[nod] != -1) {
            DF2(nod);
            comp_conexe.push_back(aux);
            aux.clear();
        }
    }

    g << comp_conexe.size() << "\n";
    for(i=0; i<comp_conexe.size(); ++i) {
        for(auto it = comp_conexe[i].begin(), it2 = comp_conexe[i].end(); it!=it2; ++it)
            g << *it << " ";
        g << "\n";
    }

    f.close();
    g.close();

    return 0;
}