BÀI TOÁN CHIA KẸO
#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;
}
// Cau truc List stack queue
typedef int ElementType;
typedef struct{
ElementType data[500];
int size;
}List;
//Khoi tao danh sach list
void make_null_list(List *L){
L->size=0;
}
void push_list(List *L, int x){
L->data[L->size]=x;
L->size++;
}
ElementType element_at_list(List* L, int i) {
return L->data[i-1];
}
int count_list(List* L) {
return L->size;
}
int empty_list(List *L)
{
return L->size == 0;
}
List neighbors(Graph *G, int x){
List L;
make_null_list(&L);
int i;
for(i=1;i<=G->n;i++)
if(adjacent(G,x,i))
push_list(&L,i);
return L;
}
//Khoi tao hang doi
typedef struct{
ElementType data[500];
int front, rear;
}Queue;
void make_null_queue(Queue *Q){
Q->front=0;
Q->rear=-1;
}
void push_queue(Queue *Q, int x){
Q->rear++;
Q->data[Q->rear]=x;
}
int top_queue(Queue *Q){
return Q->data[Q->front];
}
void pop_queue(Queue *Q){
Q->front++;
}
int empty_queue (Queue *Q){
return Q->front>Q->rear;
}
int keo[100];
void topo_sort(Graph *G,List *L){
int d[500];
int i;
for(i=1;i<=G->n;i++){
d[i]=degree_vao(G,i);
keo[i]=1;
}
Queue Q;
make_null_queue(&Q);
for(i=1;i<=G->n;i++){
if(d[i]==0){
push_queue(&Q,i);
}
}
make_null_list(L);
while(!empty_queue(&Q)){
int u=top_queue(&Q);
pop_queue(&Q);
push_list(L,u);
List L1=neighbors(G,u);
for(i=0;i<L1.size;i++){
int v=L1.data[i];
d[v]--;
keo[v]=keo[u]+1;
if(d[v]==0)
push_queue(&Q,v);
}
}
}
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",&v,&u);///doi vi tri v voi u
add_graph(&G,u,v);
}
List L;
int k=0;
topo_sort(&G,&L);
for(i=1;i<=L.size;i++){
printf("%d\n",keo[i]);
k=k+keo[i];
}
printf("%d",k);
return 0;
}