Cod sursa(job #1463258)

Utilizator retagan.mirceaRetegan Mircea retagan.mircea Data 20 iulie 2015 17:24:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include<fstream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
std::list<int> Noduri;
//long Mt[50001][50001];
vector <int> lista[50001];
int n,m;
    ofstream fout("sortaret.out");
int check(int j)
{
    for(int i = 0 ; i < n ; ++ i)
   if( find(lista[i].begin(), lista[i].end(), j) != lista[i].end())return 0;
    return 1;

}
void Sorto()
{
    while(!Noduri.empty())
    {
        int nod=Noduri.front();
         Noduri.pop_front();
        cout<<nod<<" ";
       for(int j = 0 ; j< lista[nod].size() ; ++ j)
        {
           int i=  lista[nod][j];

//lista[nod].erase(lista[nod].begin()+j-1,lista[nod].begin()+j+1);
                if(check(i))
                   {

                     Noduri.push_back(i);

                   }
            }
        }


}

int main()
{
    ifstream fin("sortaret.in");

    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y;
        fin>>x>>y;
       lista[x].push_back(y);
    }

    for(int j=1; j<=n; j++)
    {
       if(check(j))  Noduri.push_back(j);

    }

 // while(!Noduri.empty())
    //{
  //      fout<<Noduri.front()<<" ";
//Noduri.pop_front();

//}
 Sorto();
fin.close();
fout.close();
    return 0;
}