Pagini recente » Cod sursa (job #577252) | Cod sursa (job #18104) | Cod sursa (job #1679696) | Cod sursa (job #2064280) | Cod sursa (job #2143421)
#include <iostream>
#include <vector>
#include <fstream>
#define N_MAX 100001
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<int> gr[N_MAX];
int nrTati[N_MAX], n, m, ordonare[N_MAX], aux, q[N_MAX];
void solve(){ //100 puncte
int x; vector<int>::iterator it;
for(int i=1; i<=n; i++)
if(nrTati[i]==0) q[++q[0]]=i;
for(int i=1; i<=n; i++){
x=q[i];
for(it=gr[x].begin(); it!=gr[x].end(); it++){
nrTati[*it]--;
if(nrTati[*it]==0) q[++q[0]]=*it;
}
}
}
int main(){ //principiul este ca la citire numar tatii fiecarui nod. Parcurg apoi vectorul si vad cine este radacina si o adaug in coada. Parcurg apoi fiecare fiu ai nodurilor care sunt in coada
//si ii scad un tata (elimin un tata ca sa pot sa obtin urmatoarea serie de tati) daca un fiu nu mai are tati atunci el insusi e tata si il adaug in coada
f>>n>>m;
for(int i=1; i<=m; i++){
int x, y;
f>>x>>y;
gr[x].push_back(y);
nrTati[y]++;
}
solve();
for(int i=1; i<=q[0]; i++) g<<q[i]<<" ";
/*
while(n){ //50 puncte
for(int i=1; i<=aux; i++){
if(nrFii[i] == 0){
ordonare[n]=i;
n--;
nrFii[i]--;
for(int j=1; j<=aux; j++)
for(auto k: gr[j])
if(k == i)
nrFii[j]--;
}
}
}
vector<int>::iterator i;
for(i=gr[6].begin(); i!=gr[6].end(); i++)
g<<*i<<" ";*/
}