KIỂM TRA LIÊN THÔNG MẠNH

KIỂM TRA LIÊN THÔNG MẠNH 

// CT175 - Lý thuy?t d? th? (B? môn KHMT - Khoa CNTT & TT, DHCT)

// B1809362 - Truong Qu?c K?
// Gi?i thu?t d?a trên ma tr?n liên thu?c (Ð?nh - cung) cho d? th? có hu?ng và vô hu?ng

#include <stdio.h>

#define MAX_VERTICES 100
#define MAX_EDGES 500
#define MAX_ELEMENTS 100

#define white 0
#define black 1
#define gray 2

int mark[MAX_VERTICES];
int parent[MAX_VERTICES];

int color[MAX_VERTICES];
int cycle;

// C?u trúc List 
typedef int ElementType;
typedef struct {
ElementType data[MAX_ELEMENTS];
int size;
} List;


// C?u trúc Stack
typedef struct
{
    int data[MAX_ELEMENTS];
    int size;
}Stack;

// C?u trúc Queue
typedef struct
{
    int data[MAX_ELEMENTS];
    int front, rear;
}Queue;


// C?u trúc Graph
typedef struct
{
    int n, m;
    int A[MAX_VERTICES][MAX_EDGES];
}Graph;

// Cài d?t 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;
}

// Cài d?t danh sách

void make_null_list(List* L) {
    L->size = 0;
}

void push_list(List* L, ElementType 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;
}

// Cài d?t 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;
}

// Bi?n h? tr? liên thông m?nh (d? th? có hu?ng)
int num[MAX_VERTICES];
int min_num[MAX_VERTICES];
Stack S;
int on_stack[MAX_VERTICES];
int k = 0;

// T?o d? th? r?ng
void init_graph(Graph *G, int n, int m)
{
    int i, j;
    G->n = n;
    G->m = m;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            G->A[i][j] = 0;
        }
    }
}

// Thêm cung vô hu?ng
void add_edge(Graph *G, int e, int x, int y)
{
    G->A[x][e] = 1;
    G->A[y][e] = 1;
}

// Thêm cung có hu?ng
void add_vecto(Graph *G, int e, int x, int y)
{
    G->A[x][e] = 1;
    G->A[y][e] = -1;
  
}

// Nh?p danh sách cung vô hu?ng t? bàn phím
void scan_graph(Graph *G)
{
    int n, m, u, v, e;
	scanf("%d%d", &n, &m);
	init_graph(G, n, m);
	
	for (e = 1; e <= m; e++) {
		scanf("%d%d", &u, &v);
		add_edge(G, e, u, v);
	}
}

// Nh?p danh sách cung có hu?ng t? bàn phím
void scan_vecto_graph(Graph *G)
{
    int n, m, u, v, e;
	scanf("%d%d", &n, &m);
	init_graph(G, n, m);
	
	for (e = 1; e <= m; e++) {
		scanf("%d%d", &u, &v);
		add_vecto(G, e, u, v);
	}
}

// Nh?p tu?n t? ma tr?n
void scan_obo_graph(Graph *G)
{
    int n, m;
	scanf("%d%d", &n, &m);
	init_graph(G, n, m);
    int i, j;
    G->n = n;
    G->m = m;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            scanf("%d", &G->A[i][j]);
        }
    }
}

// In ma tr?n d? th?
void print_graph(Graph *G)
{
    int i, j;
    printf("\nMatrix %dx%d: \n", G->n, G->m);
    for(i = 1; i <= G->n; i++)
    {
        for(j = 1; j <= G->m; j++)
        {
            printf("%d  ", G->A[i][j]);
        }
        printf("\n");
    }
}

// Ð?c d? th? t? file (vô hu?ng) dùng add_vecto() n?u có hu?ng
void read_graph(FILE *F, Graph *G)
{
    int e, u ,v, m, n;
    fscanf(F, "%d%d", &n, &m);
    init_graph(G, n, m);
    for(e = 1; e <= m; e++)
    {
        fscanf(F, "%d%d", &u, &v);
        add_edge(G, e, u, v);
    }
}

// Ki?m tra k?
int check_adj(Graph *G, int x, int y)
{
    int j, temp;
    for(j = 1; j <= G->m; j++)
    {
        if((G->A[x][j] > 0) && (G->A[y][j] > 0))
        {
            if(x == y)
                temp = 0;
            else
            {
                temp = 1;
                break;
            }
        }
        else
            temp = 0;
    }
    return temp;
}

// Ki?m tra k? có hu?ng
int check_adj_io(Graph *G, int x, int y)
{
    int j, temp;
    for(j = 1; j <= G->m; j++)
    {
        if(((G->A[x][j] > 0) && (G->A[y][j] > 0)) || ((G->A[x][j] == 1) && (G->A[y][j] == -1)))
        {
            if(x == y)
                temp = 0;
            else
            {
                temp = 1;
                break;
            }
        }
        else if((G->A[x][j] == -1) && (G->A[y][j] == -1))
            temp = 1;
        else
            temp = 0;
    }
    return temp;
}

// B?c ra d?nh x
int degree_out(Graph *G, int x)
{
    int e, deg = 0;
    for(e = 1; e <= G->m; e++)
    {
        if(G->A[x][e] == 1)
        deg++;
    }
    return deg;
}

// B?c vào d?nh x
int degree_in(Graph *G, int x)
{
    int e, deg = 0;
    for(e = 1; e <= G->m; e++)
    {
        if(G->A[x][e] == -1)
        deg++;
    }
    return deg;
}

// Tr? v? danh sách k? d?nh x vô hu?ng
List neighbors(Graph *G, int x)
{
    int y;
    List list;
    make_null_list(&list);
    for(y = 1; y <= G->n; y++)
        if(check_adj(G, x, y))
        {
            push_list(&list, y);
        }
   return list;
}

// Tr? v? danh sách k? d?nh x có hu?ng
List neighbors_io(Graph *G, int x)
{
    int y;
    List list;
    make_null_list(&list);
    for(y = 1; y <= G->n; y++)
        if(check_adj_io(G, x, y))
        {
            push_list(&list, y);
        }
   return list;
}



// T?o l?i các d?nh chua du?c dánh d?u
void reset_mark(Graph *G)
{
    int i;
    for(i = 1; i <= G->n; i++)
        mark[i] = 0;
}

// Xoá các d?nh cha
void reset_parent(Graph *G)
{
    int i;
    for(i = 1; i <= G->n; i++)
        parent[i] = -1;
}

// Duy?t theo chi?u sâu, vô hu?ng
void DFS(Graph *G, int x)
{
    Stack S;
    make_null_stack(&S);
    push_stack(&S, x);
    parent[x] = 0;

    int i;
    while(!empty_stack(&S))
    {
        int u = top_stack(&S);
        pop_stack(&S);
        if(mark[u] == 1)
            continue;
        printf("Duyet: %d\n", u);
        mark[u] = 1;
        List L = neighbors(G, u);
        for(i = 1; i <= L.size; i++)
        {
            int v = element_at_list(&L, i);
            if(mark[v] == 0)
            {
                push_stack(&S, v);
                parent[v] = u;
            }
        }
    }    
}


// Duy?t theo chi?u r?ng, vô hu?ng
void BFS(Graph *G, int x)
{
    Queue Q;
    make_null_queue(&Q);
    push_queue(&Q, x);
    parent[x] = 0;

    int i;
    while(!empty_queue(&Q))
    {
        int u = top_queue(&Q);
        pop_queue(&Q);
        if(mark[u] == 1)
            continue;
        printf("Duyet: %d\n", u);
        mark[u] = 1;
        List L = neighbors(G, u);
        for(i = 1; i <= L.size; i++)
        {
            int v = element_at_list(&L, i);
            if(mark[v] == 0)
            {
                push_queue(&Q, v);
                parent[v] = u;
            }
        }
    }    
}

// Duy?t theo chi?u sâu d? quy, vô hu?ng
void DFS_Recursion(Graph *G, int u, int p)
{
    int i;
    if(mark[u] == 1)
        return;
    printf("Duyet: %d\n", u);
    parent[u] = p;
    mark[u] = 1;
    List L = neighbors(G, u);
    for(i = 1; i <= L.size; i++)
    {
        int v = element_at_list(&L, i);
        DFS_Recursion(G, v, u);
    }
}

// Duy?t d? quy u
void traversal(Graph *G, int u)
{
    int i;
    if(mark[u] == 1)
        return;
    mark[u] = 1;
    List L = neighbors(G, u);
    for(i = 1; i <= L.size; i++)
    {
        int v = element_at_list(&L, i);
        traversal(G, v);
    }
}

// Ð?m s? thành ph?n liên thông c?a d? th? vô hu?ng
int count_connected_components(Graph *G)
{
    int i, cmt;
    for(i = 1; i <= G->n; i++)
        if(mark[i] == 0)
        {
            traversal(G, i);
            cmt++;
        }
    return cmt;
}

// Duy?t d? quy u (chu trình vô hu?ng)
void traversal_cycle(Graph *G, int u, int p)
{
    int i;
    color[u] = gray;
    if(mark[u] == 1)
        return;
    mark[u] = 1;
    List L = neighbors(G, u);
    for(i = 1; i <= L.size; i++)
    {
        int v = element_at_list(&L, i);
        if(v == p) continue;
        if(color[v] == gray)
        {
            cycle = 1;
            return;
        }
        if(color[v] == white)
            traversal_cycle(G, v, u);
    }
    color[u] = black;
}

// Ki?m tra chu trình d? th? vô hu?ng
int contains_cycle(Graph *G)
{
    int i;
    for(i = 1; i <= G->n; i++)
        color[i] = white;
    cycle = 0;
    for(i = 1; i <= G->n; i++)
        if(color[i] == white)
            traversal_cycle(G, i, 0);
    return cycle;
}

// Duy?t d? quy u (chu trình có hu?ng)
void traversal_cycle_io(Graph *G, int u)
{
    int i;
    color[u] = gray;
    if(mark[u] == 1)
        return;
    mark[u] = 1;
    List L = neighbors_io(G, u);
    for(i = 1; i <= L.size; i++)
    {
        int v = element_at_list(&L, i);
        if(color[v] == gray)
        {
            cycle = 1;
            return;
        }
        if(color[v] == white)
            traversal_cycle_io(G, v);
    }
    color[u] = black;
}

// Ki?m tra chu trình d? th? có hu?ng
int contains_cycle_io(Graph *G)
{
    int i;
    for(i = 1; i <= G->n; i++)
        color[i] = white;
    cycle = 0;
    for(i = 1; i <= G->n; i++)
        if(color[i] == white)
            traversal_cycle_io(G, i);
    return cycle;
}

// Tìm giá tr? nh? nh?t
int min(int a, int b)
{
    int result;
    if(a < b)
        result = a;
    else
        result = b;
    return result;
}

int str = 0;
// Tìm s? thành ph?n liên thông m?nh
void strong_connect(Graph *G, int u)
{
    k++;
    num[u] = min_num[u] = k;
    push_stack(&S, u);
    on_stack[u] = 1;
    List L = neighbors_io(G, u);
    int i;
    for(i = 1; i <= L.size; i++)
    {
        int v = element_at_list(&L, i);
        if(num[v] < 0)
        {
            strong_connect(G, v);
            min_num[u] = min(min_num[u], min_num[v]);
        }
        else if (on_stack[v])
            min_num[u] = min(min_num[u], num[v]);
    }
    //printf("min_num[%d] = %d\n", u, min_num[u]);

    if(num[u] == min_num[u])
    {
        //printf("%d la dinh khop\n", u);
        int w;
        do
        {
            w = top_stack(&S);
            pop_stack(&S);
            on_stack[w] = 0;
        } while (w != u);
        str++;
    }
}

void check_strong_connect(Graph *G)
{
    int v;
    make_null_stack(&S);
    k = 1;
    for(v = 1; v <= G->n; v++)
    {
        num[v] = -1;
        on_stack[v] = 0;
    }
    for(v = 1; v <= G->n; v++)
        if(num[v] == -1)
            strong_connect(G, v);
    //printf("%d\n", str);
}


int main()
{
    // T?o m?t d? th?
    Graph dothi;

    // Bi?n l?p
   // int i, u;


    // Các thao tác

    scan_vecto_graph(&dothi);


    // Ðánh d?u các d?nh chua duy?t
    reset_mark(&dothi);
    reset_parent(&dothi);

    // Duy?t d? th?
    //for(i = 1; i <= dothi.n; i++)
    //    if(mark[i] == 0)
    //        DFS(&dothi, i);
    check_strong_connect(&dothi);
    printf("%d", str);
    
    return 0;
}