Pagini recente » Cod sursa (job #1349427) | Monitorul de evaluare | Cod sursa (job #490136) | Cod sursa (job #2477575) | Cod sursa (job #1468375)
#include <iostream>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
struct Node
{
Node()
{
value=-1;
next=NULL;
}
Node(int val)
{
value=val;
next=NULL;
}
int value;
Node *next;
};
struct List
{
Node *head;
Node *tail;
int size;
List()
{
head=NULL;
tail=NULL;
size=0;
}
void append(Node *newNode)
{
if (head==NULL)
{
head=newNode;
tail=newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
size++;
}
};
int N,M,X,Y,i,j;
List graph[50005];
vector<int> grades(50005,0),solution;
set<int> zeroGrade;
int main()
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=0;i<M;++i)
{
scanf("%d%d",&X,&Y);
grades[Y]++;
Node *newNode = new Node(Y);
graph[X].append(newNode);
}
for (i=1;i<=N;++i)
if (grades[i]==0) zeroGrade.insert(i);
while (zeroGrade.begin()!=zeroGrade.end())
{
solution.push_back(*zeroGrade.begin());
zeroGrade.erase(zeroGrade.begin());
Node * ptr= graph[solution[solution.size()-1]].head;
for (i=0;i<graph[solution[solution.size()-1]].size;++i)
{
if (--grades[ptr->value]==0)
{
zeroGrade.insert(ptr->value);
}
ptr=ptr->next;
}
}
// for (i=1;i<=N;++i)
// {
// if (grades[i]>0)
// {
// cout<<"No solution could be found"<<endl;
// return 0;
// }
// }
for (i=0;i<solution.size();i++)
printf("%d ",solution[i]);
return 0;
}