Pagini recente » Cod sursa (job #2356496) | Cod sursa (job #1261125) | Cod sursa (job #701302) | Cod sursa (job #1059603) | Cod sursa (job #755287)
Cod sursa(job #755287)
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;
FILE *in, *out;
#define MAXN 50005
vector<int> subord[MAXN];
bitset<MAXN> viz;
int n, m;
struct element_lista
{
int inf;
element_lista *urm;
};
element_lista *sortat;
void adauga_coada(element_lista *&prim, element_lista *&ultim, int inf)
{
element_lista *p = new element_lista;
p->inf = inf;
p->urm = NULL;
if(ultim != NULL)
ultim->urm = p;
ultim = p;
if(prim == NULL)
prim = ultim;
}
void afis(element_lista *vf)
{
while(vf != NULL)
{
fprintf(out, "%i ", vf->inf);
vf = vf->urm;
}
fprintf(out, "\n");
}
element_lista *prim, *ultim;
void dfs(int nod)
{
adauga_coada(prim, ultim, nod);
viz[nod] = 1;
vector<int>::iterator it;
for(it = subord[nod].begin(); it != subord[nod].end(); it++)
if(viz[*it] == 0)
dfs(*it);
}
void adauga_fii(int nod)
{
prim = ultim = NULL;
dfs(nod);
ultim->urm = sortat;
sortat = prim;
}
int main()
{
in = fopen("sortaret.in","r");
out = fopen("sortaret.out","w");
fscanf(in, "%i %i", &n, &m);
int i, nod1, nod2;
for(i = 1; i <= m; i++)
{
fscanf(in, "%i %i", &nod1, &nod2);
subord[nod1].push_back(nod2);
}
for(i = 1; i <= n; i++)
{
if(viz[i] == 0)
{
adauga_fii(i);
}
}
afis(sortat);
}