Cod sursa(job #2793426)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 3 noiembrie 2021 17:17:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <fstream>


using namespace std;

int n,m,grad_int[100005];
vector<int> graf[100005];
 ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

/*void dfs(vector<int> graf[100005],int s)
{ int i;
  viz[s]=1;
  //cout<<s<<" ";
vector<int>::iterator it;
    for ( it = graf[s].begin(); it != graf[s].end(); ++it)
       if (!viz[*it]) dfs(graf,*it);
}


void conex(  vector<int>graf[100005])
{ int i;
  for(i=1;i<=n;i++)
    if (viz[i]==0) { nrcomp++; dfs(graf,i);}
  fout<<nrcomp;
}*/

void sortare_top()
{int q[100005]={0};
    int i, x,poz=0;
     vector<int>::iterator it;

    for(x = 1; x <= n; x++)
     if(grad_int[x] == 0) q[++poz] = x;

        for(i = 1; i <= n; i++)
        {
            x = q[i];
            for(it = graf[x].begin(); it != graf[x].end(); ++it)
            {
                grad_int[*it]--;
                if(grad_int[*it] == 0) q[++poz] = *it;
            }
        }
    for(i=1;i<=n;i++)
        fout<<q[i]<<" ";


}


int main()
{
int x,y;
fin>>n>>m;
for(int i=0;i<m;i++)
    {fin>>x>>y;
    graf[x].push_back(y);
     grad_int[y]++;
  }
sortare_top();
    return 0;
}