Pagini recente » Cod sursa (job #2516519) | Cod sursa (job #3003416) | Cod sursa (job #1951928) | Cod sursa (job #1088247) | Cod sursa (job #2943107)
#include <iostream>
#include <vector>
#include <fstream>
#define MAXN 50000
using namespace std;
vector<vector<int>> v;
int inDegree[MAXN], outDegree[MAXN], c[MAXN], f[MAXN];
int main(){
int n, i, j, m, a, b, dr, st;
ifstream fin ("sortaret.in");
fin >> n >> m;
v.resize(n);
for(i = 0; i < m; i ++){
fin >> a >> b;
a --;
b --;
v[a].push_back(b);
outDegree[a] ++;
inDegree[b] ++;
}
fin.close();
st = 0;
dr = 0;
for(i = 0; i < n; i ++){
if(inDegree[i] == 0){
c[dr] = i;
f[i] = 1;
dr ++;
}
}
// for(i = 0; i < n; i ++){
// printf("%d ", inDegree[i]);
// }
// printf("\n");
while(st < dr){
int node = c[st];
st ++;
for(i = 0; i < v[node].size(); i ++){
int dest = v[node][i];
inDegree[dest] --;
if(!f[dest] && inDegree[dest] == 0){
c[dr] = dest;
f[dest] = 1;
dr ++;
}
}
}
ofstream fout ("sortaret.out");
for(i = 0; i < dr; i ++){
fout << c[i] + 1 << ' ';
}
fout.close();
return 0;
}