using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace sort_top
{
class Program
{
static void Main(string[] args)
{
int[] gi;//vectorul gradelor interioare
int n, m;
List<int>[] V;//listele vecinilor pt eficienta
int[] X;//parcugerea din BF
//citire
StreamReader fin = new StreamReader("date.in");
string linie = fin.ReadLine();//citesc o linie
string[] s = linie.Split();//o despart dupa spatiu
n = int.Parse(s[0]);//primul de pe linie
m = int.Parse(s[1]);//al doilea
X = new int[n + 1];
gi = new int[n + 1];
V = new List<int>[n + 1];//creez n+1 liste (1...n)
for (int i = 1; i <= n; i++)
V[i] = new List<int>();//creez lista de vecini pt ficare varf
for (int i = 1; i <= m; i++)
{//citeste arcele
linie = fin.ReadLine();
s = linie.Split();
int x = int.Parse(s[0]);
int y = int.Parse(s[1]);
V[x].Add(y);//adaug pe y in lista lui x (din x merg in y)
gi[y]++;//maresc gradul intern al lui y
}
int dr=0;
for (int i = 1; i <= n; i++)//adaug in X varfurile de pornire (grad interior 0)
if (gi[i] == 0) X[++dr] = i;
//parcurgere BF
int st = 1;//porneste de la primul vf din X
while (st <= dr)//cat timp mai am varfuri neparcurse
{
int v = X[st];//varful curent
for (int i = 0; i < V[v].Count; i++)//parcurg lista lui
{
int j = V[v][i];//varful din lista lui v de la pozitia i
gi[j]--;//scad gradul lui j
if (gi[j] == 0) //daca are gradul 0 (toti dinaintea lui au fost parcusi)
X[++dr] = j;//il adaug si pe j in X
}
st++;//trec la urmatorul nod din stanga lui X
}
for (int i = 1; i <= n; i++)
Console.Write(X[i] + " ");//afisez vectorul x
Console.ReadKey();
fin.Close();
}
}
}
|