Pagini recente » Cod sursa (job #1923290) | Cod sursa (job #3169193) | Cod sursa (job #2319256) | Cod sursa (job #1075349) | Cod sursa (job #1581422)
#include<fstream>
#include<stdlib.h>
#define NRMAXNXQ 50001 // numarul maxim de noduri
using namespace std;
FILE*in;
ofstream out("sortaret.out");
unsigned int nr_nxq; // numarul de noduri
long nr_arce;
unsigned int *LA[NRMAXNXQ]; // lista de adiacenta
bool visited[NRMAXNXQ];
unsigned int sorted[NRMAXNXQ];
unsigned int k; // contor pentru sorted
void read()
{
in=fopen("sortaret.in", "r");
fscanf(in, "%d%ld", &nr_nxq, &nr_arce);
// aloc memorie pentru gradul fiecarui varf
for (unsigned i=1; i<=nr_nxq; i++)
{
LA[i]=(unsigned int *)realloc(LA[i], sizeof(unsigned int));
LA[i][0]=0;
}
for (long i=1; i<=nr_arce; i++)
{
unsigned int x, y;
fscanf(in, "%d%d", &x, &y);
LA[x][0]++;
// realocam memorie pentru lista de adiacenta a lui x
LA[x]=(unsigned int *)realloc(LA[x], (LA[x][0]+1)*sizeof(unsigned int));
LA[x][LA[x][0]]=y;
}
}
void DFS(int nxq)
{
visited[nxq]=true;
for (unsigned int i=1; i<=LA[nxq][0]; i++)
if (!visited[LA[nxq][i]])
DFS(LA[nxq][i]);
k++;
sorted[k]=nxq;
}
void solve()
{
for (unsigned int i=1; i<=nr_nxq; i++)
if (!visited[i])
DFS(i);
}
void show()
{
for (unsigned int i=nr_nxq; i>=1; i--)
out<<sorted[i]<<" ";
}
int main()
{
read();
solve();
show();
return 0;
}