Tìm số thành phần liên thông của đồ thị G

Mô tả bài toán:
   Cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ thị G.


Ý tưởng thuật toán:
 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 đỉ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 kết thúc thuật toán, ngược lại quay về Bước 1.

Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: cho trong tập tin Bai1.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100).
- Dòng i+1 (1 < i < n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: xuất ra màn hình số thành phần liên thông của đồ thị.

Ví dụ:

[ Cài đặt bài toán - code Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>

//doc du lieu tu tap tin
void Doc_File(int **A,int &n) {
  FILE*f = fopen("Input.txt","rb");
  fscanf(f,"%d",&n);
  *A = new int [n];
   cout<<"Ma Tran Lien Ket Cua Do Thi";
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      cout<<endl;
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<" "<<A[i][j];
     }
  }
  fclose(f);
}

//ham tra ve so thanh phan lien thong cua do thi
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++) //khoi tao cac dinh chua danh dau
        DanhDau[i] = 0;
        do {
           j = 0;
           while(DanhDau[j]==1) //tim 1 dinh chua duoc danh dau
           j++;
           DanhDau[j] = 1; //danh dau dinh tim duoc
           Dem++; //tang so dinh danh dau len 1
           MLT++; //tang so thanh phan lien thong len 1
          do {
              ThanhCong =0;
              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;
                               Dem++;
                               if(Dem == n) return MLT;
                           }
             }while (ThanhCong == 1);
         } while(Dem<n); //lap lai khi con dinh chua duoc danh dau
    return MLT;
}

//chuong trinh chinh
void main() {
  clrscr();
   int **A,n;
   Doc_File(A,n);
   cout<<"\nTHANH PHAN LIEN THONG: "<<TPLien_Thong(A,n);
   delete *A;
   getch();

}