Cod sursa(job #2547990)

Utilizator Simon2712Simon Slanina Simon2712 Data 15 februarie 2020 22:32:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
struct ura{
  int x,y;
};
int ok=1;
ura v[100001];
bool cmp(ura a,ura b)
{
  if(a.y>b.y)
    return false;
  if(a.y==b.y && a.x>b.x)
    return false;
  return true;
}

int st[100001],dr[100001],vizit[100001];
void print(int i)
{
  vizit[i]=2;
  if(st[i]!=0 && dr[i]!=0)
    for(int j=st[i];j<=dr[i] && ok;j++)
    {
      if(!vizit[v[j].x])
        print(v[j].x);
      else
      if(vizit[v[j].x]==2) /// => impossible
        ok=0;
    }
  cout<<i<<" ";
  vizit[i]=1;
}
int main()
{
  int n,m,i;
  cin>>n>>m;
  for(i=1;i<=m;i++)
  {
    cin>>v[i].x>>v[i].y;
  }
  sort(v+1,v+m+1,cmp);
  for(i=1;i<=m;i++)
  {
    if(v[i].y!=v[i-1].y)
    {
      st[v[i].y]=i;
      dr[v[i-1].y]=i-1;
    }
  }
  dr[v[m].y]=m;
  for(i=1;i<=n && ok;i++)
  {
    if(!vizit[i])
      print(i);
  }
  return 0;
}