XẾP HẠNG STACK

 XẾP HẠNG STACK





#include<stdio.h>
#define N 500
typedef struct{
	int n;
	int A[N][N];
}Graph;
// Khoi tao do thi vo huong khong khuyen
void init_graph(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			G->A[i][j]=0;
}
void add_graph(Graph *G, int x, int y){
	G->A[x][y]=1;
//	G->A[y][x]=1;
}
int adjacent(Graph *G, int x, int y){
	return G->A[x][y]!=0;
}
int degree(Graph *G, int x){
	int deg = 0,i;
	for(i=1;i<=G->n;i++)
		if(G->A[x][i]!=0)
			deg++;
	return deg;
}
int degree_vao(Graph *G, int x){
	int i,dem=0;
	for(i=1;i<=G->n;i++)
			if(G->A[i][x]==1)
				dem++;
		return dem;
}
// Khoi tao stack
typedef int ElementType;
typedef struct{
	ElementType data[500];
	int size;
}Stack;

void make_null_stack(Stack *S){
	S->size=0;
}
void push_stack(Stack *S, int x){
	S->data[S->size]=x;
	S->size++;
}
int top_stack(Stack *S){
	return S->data[S->size-1];
}
int pop_stack(Stack *S){
	return S->size--;
}
int empty_stack(Stack *S){
	return S->size==0;
}
int rank[500];
void ranking(Graph *G){
	int d[500];
	int i;
	for(i=1;i<=G->n;i++){
		d[i]=degree_vao(G,i);
	}
	Stack S1,S2;
	make_null_stack(&S1);
	for(i=1;i<=G->n;i++)
		if(d[i]==0)
			push_stack(&S1,i);
	int k=1,v;
	while(!empty_stack(&S1)){
		make_null_stack(&S2);
		while(!empty_stack(&S1)){
			int u=top_stack(&S1);
				pop_stack(&S1);
			rank[u]=k;
			int t;
			for(t=1;t<=G->n;t++)
				if(G->A[u][t]!=0){
					d[t]--;
					if(d[t]==0)
						push_stack(&S2,t);
			}
		}
		make_null_stack(&S1);
		S1=S2;
		k++;
	}
}
int main(){
	Graph G;
	int i,n,m,e,u,v;
	freopen("dt.txt","r",stdin);
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	for(e=1;e<=m;e++){
		scanf("%d%d",&u,&v);
		add_graph(&G,u,v);
	}
	ranking(&G);
	for(i=1;i<=G.n;i++){
		printf("%d ",rank[i]);
	}
	return 0;
	
}