Cod sursa(job #1838544)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 1 ianuarie 2017 05:14:40
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 100010

using namespace std;

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

vector<int> v[N];
queue<int> coada;
int i,j,n,k,t,p,r,x,m,y,viz[N],deg[N];
void solve()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            if(viz[j]==0 && deg[j]==0)
            {
                viz[j]=1;
                g<<j<<' ';
                for(int k=0;k<v[j].size();k++)
                    deg[v[j][k]]--;
                break;
            }
    }
}
void dfs(int x)
{
    viz[x]=1;
    g<<x<<' ';
    for(int k=0;k<v[x].size();k++)
    {
        if(viz[v[x][k]]==0)
        {
        deg[v[x][k]]--;
        dfs(v[x][k]);
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        deg[y]++;
    }
    for(i=1;i<=n;i++)
        if(deg[i]==0 && viz[i]==0)
        dfs(i);
}