Pagini recente » Cod sursa (job #1078767) | Cod sursa (job #1799813) | Cod sursa (job #765641) | Cod sursa (job #2588105) | Cod sursa (job #626345)
Cod sursa(job #626345)
#include <stdio.h>
#include <vector>
using namespace std;
#define maxn 50010
vector <int> lista[maxn];//lista[i][] lista vecinilor nodului i
int grad[maxn],coada[maxn];//grad[i]=nr de arce care intra in i
int main(){
int n,m;
FILE *fin=fopen("sortaret.in","r");
fscanf(fin,"%d%d",&n,&m);
int i,a,b;
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a,&b);
lista[a-1].push_back(b-1);
grad[b-1]++;
}
//incep parcurgerea...O(n^2);
int li=0,ls=0;
FILE *fout=fopen("sortaret.out","w");
//adaug totate nodurile care initial au gradul exterior 0, in coada
for(i=0;i<n;i++)
if(grad[i]==0)coada[ls++]=i;
//ls++;
while(li<ls){
//iau coada[li] si expandez cu toti vecinii sai care in urma scaderii au grad nul
for(i=0;i<lista[coada[li]].size();i++){
grad[lista[coada[li]][i]]--;//scad gradul tuturor vecinilor
if(grad[lista[coada[li]][i]]==0){
//daca in urma scaderii sunt grade nule, le adaug in coada
coada[ls++]=lista[coada[li]][i];
}
}
li++;
}
for(i=0;i<n;i++)fprintf(fout,"%d ",coada[i]+1);
fprintf(fout,"\n");
fclose(fout);
return 0;
}