Pagini recente » Rating Ovidiu Cojocaru (ocojocaru) | Cod sursa (job #1340565) | Cod sursa (job #49072) | Cod sursa (job #191355) | Cod sursa (job #1468346)
#include <iostream>
#include <string.h>
#include <vector>
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++;
}
void print()
{
Node * ptr=head;
while (ptr)
cout<<ptr->value<<" ",
ptr=ptr->next;
cout<<endl;
}
};
int N,M,X,Y,i,j;
List graph[50005];
vector<int> grades(50005,0),zeroGrade,solution;
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.push_back(i);
while (zeroGrade.size()!=0)
{
solution.push_back(zeroGrade[0]);
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.push_back(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("%s ",solution[i]);
return 0;
}