Cod sursa(job #1468361)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 5 august 2015 21:08:21
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#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++;
	}
	
};

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("%d ",solution[i]);
    return 0;
}