Đếm số thành phần liên thông của đồ thị vô hướng G

BÀI TOÁN
Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với:
- A[i,j] = 1 nếu có đường đi từ i đến j, A[i,j] = 0 nếu không có đường đi từ i đến j.
- A[i,j] = A[j,i].
Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Toán 2.
Dữ liệu ra: hiển thị số thành phần liên thông của đồ thị ra màn hình.
Ví dụ:
BAI3.INP
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
MIEN LIEN THONG: 2

BAI3.INP
5
0 0 0 0 1
0 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
MIEN LIEN THONG: 1

HƯỚNG DẪN THUẬT TOÁN
Ý tưởng: Sử dụng thuật toán loang giống như bài toán 2.
Bước 0: Khởi tạo số thành phần liên thông bằng 0.
Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2.
Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu tất cả các đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang bước 3.
Bước 3: Thực hiện bước 2 cho đến khi không còn thực hiện được nữa chuyển sang bước 4.
Bước 4: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật toán và trả về số thành phần liên thông, ngược lại quay về bước 1.
Chú ý: Nếu số thành phần liên thông bằng 1 đồ thị liên thông.

CHƯƠNG TRÌNH MẪU

Code:

/*Hàm trả về số thành phần liên thông của đồ thị vô hướng */
int TPLien_Thong(int **A, int n) {
  char*DanhDau = new char [n];
  char ThanhCong;
  int Dem=0, i,j, MLT=0;
  for( i = 0; i<n; i++)        //Khởi tạo mọi đỉnh chưa được đánh dấu
      DanhDau[i] = 0;
  do { 
    j = 0;
      while(DanhDau[j]==1)  //B1: Tìm 1 đỉnh chưa được đánh dấu
        j++;
      DanhDau[j] = 1;      //Đánh dấu đỉnh tìm được
      Dem++;        //Tăng số đỉnh được đánh dấu lên 1
      MLT++;        //Tăng miền liên thông lên 1
      do {
        ThanhCong =0;  //Giả sử không còn khả năng loang
        for(i = 0; i<n; i++)
        if(DanhDau[i]==1)
            for(j = 0; j<n; j++)
            if (DanhDau[j] == 0 && A[i][j] > 0) {
              DanhDau[j] = 1;
              ThanhCong =1;  //Còn khả năng loang
              Dem++;
              if(Dem == n) return MLT;
            }
      }while (ThanhCong == 1);  //Lặp khi còn khả năng loang
  } while(Dem<n);        //Lặp khi còn tồn tại đỉnh chưa được dánh dấu
  return MLT;
}