Cod sursa(job #2657599)

Utilizator patriciaxdBraica Patricia patriciaxd Data 11 octombrie 2020 10:55:34
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
//sortare topologica
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
set <int> S;
vector < int >lista[50005];
vector <int >v;
int nr[50005];
set <int>::iterator it;
int n,m;
void sortare()
{ while(!S.empty())
  {   it=S.begin();
      int nod=*it;
      S.erase(nod);
      v.push_back(nod);
      for(int i=1;i<=n;i++)
       for(int j=0;j<lista[i].size();j++)
          if(lista[i][j]==nod)
            {lista[i][j]=0;
             nr[i]--;
             if(!nr[i])
                lista[i].clear();
              if(lista[i].empty())
                S.insert(i);
            }
  }

}
int main()
{ in>>n>>m;
   int x,y;//varfurile x->y
for(int i=1;i<=m;i++)
    { in>>x>>y;
     bool ok=1;
     for(int j=0;j<lista[y].size();j++)
        if(lista[y][j]==x)
        { ok=0;
          break;
        }
        if(ok)
       lista[y].push_back(x);
    }
 for(int i=1;i<=n;i++)
       {if(lista[i].empty())
         S.insert(i);
         nr[i]=lista[i].size();
         }
 sortare();
 for(int i=0;i<v.size();i++)
        out<<v[i]<<' ';
    return 0;
}