Pagini recente » Cod sursa (job #2705669) | Cod sursa (job #2911327) | Istoria paginii runda/inca_vacanta_ix/clasament | Cod sursa (job #2604436) | Cod sursa (job #2456701)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef struct node
{
int val;
node* next;
};
int N, M;
node* vecini[50001];
int viz[50001];
int grad[50001];
void read_data(const char* filename)
{
FILE* fp = fopen(filename, "r");
fscanf(fp, "%d%d", &N, &M);
for (int i = 1; i <= N; i++)
{
viz[i] = 0;
vecini[i] = NULL;
grad[i] = 0;
}
for (int i = 0; i < M; i++)
{
int a, b;
fscanf(fp, "%d%d", &a, &b);
node* nou = new node;
nou->val = b;
grad[b]++;
nou->next = vecini[a];
vecini[a] = nou;
}
fclose(fp);
}
void DFS(int nod,FILE* fout)
{
fprintf(fout,"%d ", nod);
viz[nod] = 1;
for (node* p = vecini[nod]; p != NULL; p = p->next)
{
grad[p->val]--;
if (viz[p->val] == 0)
{
DFS(p->val,fout);
}
}
}
void topological_sort()
{
FILE* fout = fopen("sortaret.out", "w");
for (int i = 1; i <= N; i++)
{
if (viz[i] == 0 && grad[i]==0)
{
DFS(i,fout);
}
}
fclose(fout);
}
int main()
{
read_data("sortaret.in");
topological_sort();
}