Pagini recente » Cod sursa (job #1679137) | Monitorul de evaluare | Cod sursa (job #3294471) | Cod sursa (job #173400) | Cod sursa (job #1899210)
#include <stdio.h>
class list {
int n, *v;
public:
list() {
n = 0;
v = NULL;
}
void push(int el) {
if ((n & (n-1)) == 0) {
int max = n ? 2*n : 1;
int *p = new int[max];
for (int i = 0; i < n; ++i) {
p[i] = v[i];
}
delete v;
v = p;
}
v[n++] = el;
}
int operator[] (int u) {
return v[u];
}
int len() {
return n;
}
};
list *G;
int *q, l, r;
bool *viz, *tata;
int main()
{
FILE *fin, *fout;
fin = fopen("sortaret.in", "r");
fout = fopen("sortaret.out", "w");
int N, M;
fscanf(fin, "%d%d", &N, &M);
G = new list[N + 1]();
tata = new bool[N + 1]();
for (int i = 1; i <= M; ++i) {
int x, y;
fscanf(fin, "%d%d", &x, &y);
G[x].push(y);
tata[y] = 1;
}
q = new int[N + 1];
viz = new bool[N + 1];
for (int i = 1; i <= N; ++i) {
if (!tata[i]) {
q[r++] = i;
viz[i] = 1;
}
}
while (r != l) {
int nod = q[l];
fprintf(fout, "%d ", nod);
for (int i = 0; i < G[nod].len(); ++i) {
if (!viz[G[nod][i]]) {
viz[G[nod][i]] = 1;
q[r++] = G[nod][i];
}
}
++l;
}
fclose(fin);
fclose(fout);
return 0;
}