Pagini recente » Cod sursa (job #1395454) | Cod sursa (job #1364716) | Cod sursa (job #96228) | Cod sursa (job #1199156) | Cod sursa (job #2657599)
#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;
}