Cod sursa(job #943526)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 25 aprilie 2013 17:57:19
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<vector>
using namespace std;

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

const int MAXN = 200010;
int N, M, x, y, fiu, nod, u, s[MAXN], h1, h2;
bool used[MAXN];
vector <int> G[MAXN], F[MAXN];


void DFS_suc(int nod){
    int i;
    //fout << nod << " ";
    used[nod] = 1;
    for(i=0; i<G[nod].size(); ++i)
    {
        y = G[nod][i];
        if(used[y] == 0)
            DFS_suc(y);
    }
    s[++h1] = nod;
}

void DFS_pred(int nod){
    int i;
    used[nod] = 1;
    for(i=0; i<F[nod].size(); ++i)
    {
        y = F[nod][i];
        if(used[y] == 0)
            DFS_pred(y);
    }
    fout << nod << " ";
}

int main(){
    int i, j;
    fin >> N >> M;
    for(i=0; i<M; ++i){
        fin >> nod >> fiu;
        G[nod].push_back(fiu);
        F[fiu].push_back(nod);
    }

    for(i=1; i<=N; ++i)
        if(!used[i])
            DFS_suc(i);

    for(i=1; i<=N; ++i)
        used[i] = 0;

    for(i=N; i>0; --i)
        if(!used[s[i]]){
            DFS_pred(s[i]);
            fout << "\n";
        }


    fin.close();
    fout.close();

    return 0;
}