Pagini recente » Cod sursa (job #1760336) | Cod sursa (job #2072925) | Cod sursa (job #2194013) | Cod sursa (job #345727) | Cod sursa (job #626319)
Cod sursa(job #626319)
#include <stdio.h>
#include <vector>
using namespace std;
#define maxn 50010
vector <int> lista[maxn];//lista[i][] lista vecinilor nodului i
int grad[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].push_back(b);
grad[b]++;
}
//incep parcurgerea...O(n^2);
int j,aux;
FILE *fout=fopen("sortaret.out","w");
for(i=0;i<n;i++){
//pt nodul i, gradul sau interior este grad[i]; este el 0?
if(grad[i]==0){
fprintf(fout,"%d ",i+1);
//scot nodul i (scad cu 1 gradele interioare ale tuturor nodurilor vecine cu i)
for(j=0;j<lista[i].size();j++)
if(grad[lista[i][j]]!=0)grad[lista[i][j]]--;//daca e 0, inseamna ca l-am scos deja
}
}
return 0;
}