BÀI TOÁN PHẦN MỀM THI CÔNG Adjacency Matrix

 BÀI TOÁN PHẦN MỀM THI CÔNG Adjacency Matrix

//Thi Cong // Adjacency Matrix (Vertices-Vertices) [Directed]

#include <stdio.h>

#define MAX_ELEMENTS 100

//List Structure
typedef int ElementType;
typedef struct {
ElementType data[MAX_ELEMENTS];
int size;
}List;

//Stack Structure
typedef struct
{
    int data[MAX_ELEMENTS];
    int size;
}Stack;

//Queue Structure
typedef struct
{
    int data[MAX_ELEMENTS];
    int front, rear;
}Queue;

/* Init List */

//Make null a list
void make_null_list(List* L) {
    L->size = 0;
}

//Pust List
void push_list(List* L, ElementType x) {
    L->data[L->size] = x;
    L->size++;
}

//Return an element at list
ElementType element_at_list(List* L, int i) {
    return L->data[i-1];
}

//Count amount element in list
int count_list(List* L) {
    return L->size;
}

//Empty a list
int empty_list(List *L)
{
    return L->size == 0;
}

//Copy list
void copy_list(List* L1, List* L2)
{
	int i;
	make_null_list(L1);
	for(i = 1; i <= L2->size; i++)
	{
		push_list(L1, element_at_list(L2, i));
	}
}

/* Init Queue */

//Make null a queue
void make_null_queue(Queue *Q)
{
    Q->front = 0;
    Q->rear = -1;
}

//Push Queue
void push_queue(Queue *Q, int x)
{
    Q->rear++;
    Q->data[Q->rear] = x;
}

//Top Queue
int top_queue(Queue *Q)
{
    return Q->data[Q->front];
}

//Pop Queue
void pop_queue(Queue *Q)
{
    Q->front++;
}

//Empty a Queue
int empty_queue(Queue *Q)
{
    return Q->front>Q->rear;
}

/* Init Stack */

//Make null a stack
void make_null_stack(Stack *S)
{
    S->size = 0;
}

//Push Stack
void push_stack(Stack *S, int x)
{
    S->data[S->size] = x;
    S->size++;
}

//Top stack
int top_stack(Stack *S)
{
    return S->data[S->size - 1];
}

//Pop stack
int pop_stack(Stack *S)
{
    return S->size--;
}

//Empty a stack
int empty_stack(Stack *S)
{
    return S->size == 0;
}

#define MAX 200
#define INFINITY 999999

int d[MAX];
int t[MAX];
int T[MAX];

//Graph Structure
typedef struct
{
    int n;
    int A[MAX][MAX];
}Graph;


/* Init A Basic Graph */

//Init an empty graph
void init_graph(Graph* G, int n)
{
    int i, j;
    G->n = n;
    for(i = 1;  i <= n; i++)
        for(j = 1; j <= n; j++)
            G->A[i][j] = 0;
}

// Add an edge
void add_vecto(Graph *G, int x, int y)
{
    G->A[x][y] = 1;
    G->A[y][x] = -1;
}

//Scan any edge
void scan_vecto_graph(Graph *G, int* work_at, int* start)
{
	int n, u, v, x;
//	freopen("DuAnXayNha.txt","r",stdin);
	scanf("%d", &n);
	init_graph(G, n+2);
	d[n+1] = 0;	
	for(u = 1; u <= n; u++)
	{
		scanf("%d", &d[u]);
		do{
			scanf("%d", &x);
			if (x>0) add_vecto(G,x,u);
		} while(x>0);
	}
	
	//scanf("%d%d", work_at, start);
	for(u = 1; u <= n; u++)
	{
		int deg_neg = 0;
		for(x = 1; x <= n; x++)
			if(G->A[x][u] > 0)
				deg_neg++;
		if(deg_neg == 0 )
			add_vecto(G, n+1, u);
	}
	
	for(u = 1; u <= n; u++)
	{
		int deg_pos = 0;
		for(v = 1; v <= n; v++)
			if(G->A[u][v] > 0)
				deg_pos++;
		if(deg_pos == 0)
			add_vecto(G, u, n+2);
	}
}


//Return IN degree of a vertice
int degree_in(Graph* G, int x)
{
    int y, deg = 0;
    for(y = 1; y <= G->n; y++)
        if(G->A[x][y] < 0)
            deg++;
    return deg;
}

//Has edge
int has_edge(Graph* G, int x, int y)
{
    return ((G->A[x][y] != 0) && (G->A[y][x] != 0)) ? 1 : 0;
}

//Check Adjacency
int check_direction(Graph* G, int x, int y)
{
    return ((G->A[x][y] == 1) && (G->A[y][x] == -1)) ? 1 : 0;
}

//Return Out Vertical Neighbor List ++
List neighbors_out(Graph *G, int x)
{
    int y;
    List list;
    make_null_list(&list);
    for(y = 1; y <= G->n; y++)
        if(check_direction(G, x, y) && has_edge(G, x, y))
        {
            push_list(&list, y);
        }
   return list;
}

void TopoSort(Graph* G, List* L)
{
	int u, d[MAX];
	Queue Q;
	make_null_queue(&Q);
	for(u = 1; u <= G->n; u++)
		d[u] = 0;
	for(u = 1; u <= G->n; u++)
		d[u] = degree_in(G, u);
	for(u = 1; u <= G->n; u++)
		if(d[u] == 0)
			push_queue(&Q, u);
	make_null_list(L);
	while(!empty_queue(&Q))
	{
		int u = top_queue(&Q); pop_queue(&Q);
		push_list(L, u);
		int v;
		for(v = 1; v <= G->n; v++)
		{
			if(has_edge(G, u, v))
			{
				d[v]--;
				if(d[v] == 0)
					push_queue(&Q, v);
			}
		}
	}
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int max(int a, int b)
{
	return a < b ? b : a;
}

void ThiCong(Graph* G, List* L)
{
	int n = G->n - 2;
	t[n+1]=  0;
	int i, v;
	for(i = 2; i <= L->size; i++)
	{
		int u = element_at_list(L, i);
		t[u] = -1;
		for(v = 1; v <= G->n; v++)
			if(check_direction(G, v, u))
				t[u] = max(t[u], t[v] + d[v]);
	}
	
	T[n+2] = t[n+2];
	for(i = L->size - 1; i >= 1; i--){
		int u = element_at_list(L,i);
		T[u] = INFINITY;
		for (v = 1; v <= G->n; v++)
			if(check_direction(G, u, v))
				T[u] = min(T[u], T[v] - d[u]);
	}
}

int main()
{
	int work_at, start;
	Graph dothi;
	scan_vecto_graph(&dothi, &work_at, &start);
	List L;
	TopoSort(&dothi, &L);
	ThiCong(&dothi, &L);
	int j;
	for(j=1;j<=dothi.n;j++)
		if(T[j]==t[j])
			printf("%d\n",j);

	return 0;
}