Cod sursa(job #1963425)

Utilizator dica69Alexandru Lincan dica69 Data 12 aprilie 2017 15:24:15
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
/*
    skel_graph - DFS
*/

#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <bitset>
#include <cassert>
#include <stack>
#define NMAX 100009 // ATENTIE la cat e in problema curenta !!!
#define MMAX 500009 // ATENTIE la cat e in problema curenta !!!

using namespace std;

int n, m;
int p[NMAX];
vector<int> G[NMAX];
vector<int> Gtr[NMAX];
bitset<NMAX> used;

void read_input() {
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >>  x >> y;

        G[x].push_back(y);
    }
}


void dfs(int node, stack<int>& st) {
    used[node] = 1;

    for (auto it = G[node].begin(); it != G[node].end(); ++it) {
        if (!used[ *it ]) {
            dfs(*it, st);
        }
    }
    st.push(node);
}

void dfsT(int node) {
    used[node] = 1;
    cout << node << " ";

    for (auto it = Gtr[node].begin(); it != Gtr[node].end(); ++it) {
        if (!used[ *it ]) {
            dfsT(*it);
        }
    }
}


void ctc() {
    stack<int> st;

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, st);
        }
    }

    // Get graph transpose    
    for (int i = 1; i <= n; i++) {
        for (auto it = G[i].begin(); it != G[i].end(); ++it) {
            Gtr[*it].push_back(i);
        }
    }

    for (int i = 0; i <=n; i++) {
        used[i] = 0;
    }

    while (!st.empty()) {
        int v = st.top();
        st.pop();

        if (!used[v]) {
            dfsT(v);
            cout << "\n";
        }
    }

}


void print_output() {
}


// puteti pastra main-ul mereu cum e acum
int main() {
    // las linia urmatoare daca citesc din fisier
    assert( freopen("in", "r", stdin) != NULL);

    // las linia urmatoare daca afisez in fisier
    // assert( freopen("out", "w", stdout) != NULL) ;

    read_input();
    ctc();
    print_output();

    return 0;
}