Cod sursa(job #1468375)

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