1480 - Hệ thống mạng

#include <stdio.h>
#include <stdlib.h>

#define MAX 50

typedef struct GRAPH {
    int n; // Số đỉnh
    int a[MAX][MAX]; // Ma trận kề
} DoThi;

// Hàm tìm các đỉnh liên thông
void DiTimCacDinhLienThong(DoThi g, int Nhan[], int i) {
    for(int j = 1; j <= g.n ; j++) {
        if(g.a[i][j] != 0 && Nhan[j] != Nhan[i]) {
            Nhan[j] = Nhan[i];
            DiTimCacDinhLienThong(g, Nhan, j);
        }
    }
}

// Hàm xét tính liên thông và in kết quả
void XetLienThong(DoThi g) {
    int Nhan[MAX];
    
    for(int i=1;i<=g.n;i++)
        Nhan[i] = 0;
    
    int SoThanhPhanLT = 0;
    
    for(int i=1;i<=g.n;i++) {
        if(Nhan[i] ==0) {
            SoThanhPhanLT++;
            Nhan[i] = SoThanhPhanLT;
            DiTimCacDinhLienThong(g, Nhan, i);
        }
    }
    
    printf ("%d\n",SoThanhPhanLT); 
}

void HeThongMang(DoThi &g) {
    int n, m; // Đọc số đỉnh và số cạnh của đồ thị
    scanf("%d %d", &n, &m);
    g.n = n; // Gán số đỉnh của đồ thị
    
    // Khởi tạo ma trận kề
    for(int i = 1 ; i <= g.n ; i++) {
        for(int j = 1 ; j <= g.n ; j++)
            g.a[i][j] = 0;
    }
    
    // Đọc thông tin về các cạnh và cập nhật ma trận kề
    for(int i = 1; i <= m ; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g.a[x][y] = i; // i là chỉ số của cạnh trong ma trận
        g.a[y][x] = i; // Gán cả 2 chiều vì đồ thị vô hướng
    }
 
    // Đọc số lượng truy vấn ngắt cạnh và xử lý
    int k;
    scanf("%d", &k);
    for(int o = 1; o <= k ; o++) {
        // Sao chép đồ thị gốc
        DoThi Temp = g;
        
        // Đọc thông tin về khoảng ngắt cạnh từ l đến r
        int l, r;
        scanf("%d%d", &l, &r);
        
        // Ngắt/loại các cạnh có chỉ số trong khoảng [l, r]
        for (int i = 1; i <= Temp.n; i++) {
            for (int j = 1; j <= Temp.n; j++) {
                if (Temp.a[i][j] >= l && Temp.a[i][j] <= r) {
                    Temp.a[i][j] = 0;
                }
            }
        }
        
        // Xét lại tính liên thông sau khi ngắt
        XetLienThong(Temp);
    }
}

int main() {
    DoThi g;
    HeThongMang(g);
    return 0;
}