Pagini recente » Cod sursa (job #783439) | Cod sursa (job #851741) | Cod sursa (job #2048378) | Cod sursa (job #2726483) | Cod sursa (job #507412)
Cod sursa(job #507412)
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#define maxn 100000
#define maxm 50000
using namespace std;
vector<int> *v = new vector<int> [maxn];
vector<int> noi (maxn);
vector<int> visited (maxn);
vector<int> final;
void getNoIncoming()
{
int i;
for (i = 0; i < maxn; i++) {
for(int j = 0; j < v[i].size(); j++) {
noi[v[i][j]] = 1;
}
}
}
void bfs(int x) {
int i;
for (i = 0; i < v[x].size(); i++) {
bfs(v[x][i]);
}
if (!visited[x]) {
visited[x] = 1;
final.push_back(x);
}
}
int main() {
unsigned int i, x, y, n, m;
FILE *f = fopen("sortaret.in", "rt");
FILE *g = fopen("sortaret.out", "wt");
fscanf(f , "%d%d", &n, &m);
for (i = 0; i < n; i++) {
fscanf(f, "%d%d", &x, &y);
v[--x].push_back(--y);
}
/* for (i = 0; i < n; i++) {
cout << i << " ";
for (int j = 0; j < v[i].size();j++) {
cout << v[i][j] << " ";
}
cout << endl;
} */
getNoIncoming();
for (i = 0; i < n; i++) {
if (noi[i] == 0)
bfs(i);
}
for (vector<int>::reverse_iterator it = final.rbegin(); it != final.rend(); ++it) {
fprintf(f, "%d", *it + 1);
}
fclose(f);
fclose(g);
return 0;
}