Cod sursa(job #2530534)

Utilizator valispartanuStefan Valentin Popescu valispartanu Data 24 ianuarie 2020 21:47:01
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> g[50005];
int n,m,x,y;
bool viz[50005]= {false};

ifstream f ("sortaret.in");
ofstream o ("sortaret.out");


void DFS(int node)
{
    if(!viz[node])
    {
        viz[node] = true;
        o<<node<<" ";
        for(int i=0; i<g[node].size(); i++)
        {
            DFS(g[node][i]);
        }
    }
}

void DFSit(int node)
{
    memset(viz, false, sizeof(viz));
    stack<int> s;
    s.push(node);
    while(!s.empty())
    {
        int nod=s.top();
        s.pop();
        if(!viz[nod])
        {
            viz[nod] = true;
            cout<<nod<<"\n";
            for(int i=0; i<g[nod].size(); i++)
            {
                s.push(g[nod][i]);
            }
        }
    }
}

void BFS(int node)
{
    memset(viz, false, sizeof(viz));
    queue<int> q;
    q.push(node);
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        if(!viz[nod])
        {
            viz[nod] = true;
            cout<<nod<<"\n";
            for(int i=0; i<g[nod].size(); i++)
            {
                q.push(g[nod][i]);
            }
        }
    }
}

int main()
{
    f>>n>>m;
    int a[50005]={0};
    for(int i=1; i<=m; i++)
    {
        f>>x>>y;
        a[y]++;
        g[x].push_back(y);
    }
    for(int j=1;j<n; j++){
        if(a[j]==0){
            DFS(j);
        }
    }
    //DFS(1);
    //cout<<endl;
    //DFSit(1);
    //cout<<endl;
    //BFS(1);
    return 0;
}