Cod sursa(job #457652)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 20 mai 2010 20:28:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
using namespace std;
#include <fstream>
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, s[100005], nr;
 
struct nod
{
    int inf;
    nod *urm;
} * v[100005];
 
void add(nod *&prim, int val)
{
    nod * p, *q;
	p = new nod;
    p -> inf = val;
    p -> urm = NULL;
	if (prim)
	{
		for(q=prim;q->urm;q=q->urm);
	q->urm=p;
	}
	else
	prim=p;
    
}
 
void citire()
{
    fin>>n>>m;
    int i, x, y;
 
    for (i = 1; i <= m; i++)
    {
        fin>>x>>y;
        add(v[x], y);
    }
}
 
void dfs(int x)
{
    nod * p;
    s[x] = 1; fout<<x<<" ";
    for (p = v[x]; p != NULL; p = p -> urm) if (!s[p -> inf]) dfs(p -> inf);
}  
 
int main()
{
    citire();
    for (int i = 1; i <= n; i++) 
		if (!s[i]) 
		  { dfs(i);nr++;}
        return 0;
}