Code C++: Tìm kiếm nhị phân không sử dụng đệ quy

#include<stdio.h>
#include<iostream>
using namespace std;
int a[100],n,x;
int TimKiemNhiPhan(int M[], int N, int X){
int First = 0;
int Last = N - 1;
while (First <= Last){
int Mid = (First + Last)/2;
if (X == M[Mid])
return Mid;
if (X < M[Mid])
Last = Mid - 1;
else
First = Mid + 1;
}
return -1;
}
void nhap(){
cout<<"Nhap so phan tu mang: "; cin>>n;
for(int i=0;i<n;i++){
cout<<"a["<<i<<"]= "; cin>>a[i];
}
cout<<"Nhap so can tim: "; cin>>x;
}
int main(){
nhap();
cout<<"So lan xuat hien: "<<TimKiemNhiPhan(a,n,x);
return 0;
}

More about →

Code C++: Tìm kiếm tuần tự

#include<stdio.h>
#include<iostream>
using namespace std;
int a[100],n,x;
int TimKiemTuanTu (int M[], int N, int X){
int k = 0;
while (M[k] != X && k < N)
k++;
if (k < N)
return k;
return 0;
}
void NhapMang(){
cout<<"Nhap so phan tu mang: "; cin>>n;
for(int i=0;i<n;i++){
cout<<"a["<<i<<"]= "; cin>>a[i];
}
        cout<<"Nhap so can tim: "; cin>>x;
}
int main(){
NhapMang();
cout<<"So lan xuat hien: "<<TimKiemTuanTu(a,n,x);
return 0;
}
Tag: Kỹ thuật lập trình, Tìm kiếm tuần tự, Linear Search, Cấu trúc dữ liệu và giải thuật

More about →

Code C/C++: Thuật toán Kruskal tìm cây bao trùm tối thiểu

Mô tả bài toán: Cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất. Tức là tìm đồ thị con liên thông  G' ⊆ G sao cho tổng trọng số của G’ là nhỏ nhất.
Ý tưởng thuật toán:
Bước 0: khởi tạo tập cạnh tìm được là rỗng và chuyển sang Bước 1.
Bước 1: chọn một cạnh có trọng số nhỏ nhất sao cho khi đưa cạnh này vào tập cạnh tìm được không tạo thành chu trình. Tăng số cạnh tìm được lên 1  và chuyển sang Bước 2.

Bước 2: nếu số cạnh tìm được bằng n-1 thuật toán kết thúc, 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: lưu trong tập tin Bai8.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) lưu ma trận kề của đồ thị với 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: lưu trong file Kruskal.out
-  Dòng đầu ghi trọng số nhỏ nhất của cây bao trùm.

-  Các dòng còn lại lưu đường đi giữa đỉnh i nối với đỉnh j.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"
typedef structEgde {
      int x,y;
};
//đọc dữ liệu từ tập tin
void Doc_File(int **A,int &n)  {
    FILE*f = fopen(FileInt,"rb");
    fscanf(f,"%d",&n);
    *A = new int [n];
    for(int i =0;i<n;i++) {
       A[i] = new int [n];
       for(int j =0;j<n;j++) {
           fscanf(f,"%d",&A[i][j]);
       }
    }
    fclose(f);
}
//ghi dữ liệu ra tập tin
void Ghi_File(Egde*L,int n,int Sum) {
    FILE*f = fopen(FileOut,"wb");
    fprintf(f,"%d\n",Sum);
    for(int i =0; i<n-1; i++)
    fprintf(f,"%d -%d\n",L[i].x+1,L[i].y+1);
    fclose(f);
}
void Kruskal(int **A, int n) {
    int *D = new int[n];

    Egde *L = new Egde[n-1]; 
    int min = MAXINT, Dem = 0, Sum = 0, T = 0, Temp;
    for(int i=0; i<n; i++)
        D[i] = 0;
        do{
            min = MAXINT;
            for( i=0; i<n; i++)
                 for(int j=0; j<n; j++)
                      if(A[i][j]>0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) {
                          min = A[i][j];
                          L[Dem].x = i;
                          L[Dem].y = j;
                      }
                      if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){
                          T++;
                          D[L[Dem].x] = D[L[Dem].y] = T;
                      }
                      if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0){
                          D[L[Dem].x] = D[L[Dem].y];
                      }
                      if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0){
                          D[L[Dem].y] = D[L[Dem].x];
                      }
                      if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0) {
                          Temp = D[L[Dem].x];
                          for( i=0; i<n; i++)
                             if(Temp==D[i])
                                   D[i]=D[L[Dem].y];
                      }
                   Sum+=min;
                   Dem++;
      } while(Dem<n-1);
      Ghi_File(L,n,Sum);
}
//chương trình chính
int main() {
         int **A,n;
         Doc_File(A,n);
         Kruskal(A,n);
         delete *A;
         return 0;
}
Từ khóa: ky thuat lap trinh, kỹ thuật lập trình, Kruskal, cây bao trùm tối thiểu, programming, algorithm, toán rời rạc, cây, cau truc du lieu, giai thuat.

More about →

Code C/C++: Thuật toán Prim tìm cây bao trùm tối thiểu

Mô tả bài toán: cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất.
Ý tưởng thuật toán:
Bước 1: xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh đó và số cạnh tìm được là 1. Chuyển sang Bước 2.
Bước 2: tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu. Nghĩa là, ta tìm min{A[i][j]} j=1..n, i=1..n sao cho i đánh dấu và j chưa đánh dấu để tránh trường hợp tạo thành chu trình con. Ta tăng số cạnh tìm được lên 1 và chuyển sang Bước 3.
Bước 3: nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về Bước 2.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: lưu trong tập tin Bai7.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) lưu ma trận kề của đồ thị với 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: lưu trong file Bai7.out
-  Dòng đầu ghi trọng số nhỏ nhất của cây bao trùm.
-  Các dòng còn lại lưu đường đi giữa đỉnh i nối với đỉnh j.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <values.h>
#define max 100
#define FileInt "Bai7.inp"
#define FileOut "Bai7.out"
typedef struct Egde{
int x,y;
}; 
//đọc dữ liệu từ tập tin
void Doc_File(int A[max][max],int &n) {
FILE*f = fopen(FileInt,”rb”);
fscanf(f,”%d”,&n);
for(int i =0;i<n;i++) {
for(int j =0;j<n;j++) {
fscanf(f,”%d”,&A[i][j]);
}
}
fclose(f);
}
//ghi dữ liệu ra tập tin
void Ghi_File(Egde L[max],int n,int Sum) {
FILE*f = fopen(FileOut,"wb");
fprintf(f,"%d\n",Sum);
for(int i =0; i<n-1; i++)
fprintf(f,"%d -%d\n",L[i].x+1,L[i].y+1);
fclose(f);
}
//thuật toán Prim
void Prim(int A[max][max], int n) {
char D[max];
Egde L[max];
int min = MAXINT, Dem = 0, Sum = 0;
for(int i=0; i<n; i++)
D[i]=0;
for(int j=1; j<n; j++)
if(min>A[0][j] && A[0][j]!=0){
min = A[0][j];
L[0].y = j;
}
L[0].x = 0;
D[0] = 1;
D[L[0].y] = 1;
Sum+=min;
Dem++;
do {
min = MAXINT;
for( i=0; i<n; i++)
if(D[i]==1)
for( j=0; j<n; j++)
if(A[i][j]>0 && min>A[i][j] && D[j]==0){
min = A[i][j]; 
L[Dem].x = i;
L[Dem].y = j;
}
Sum+=min;
D[L[Dem].y] = 1;
Dem++;
} while(Dem<n-1);
Ghi_File(L,n,Sum);
}
//chương trình chính
void main() {
int A[max][max],n;
Doc_File(A,n);
Prim(A,n);

}
Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, prim, cây khung

More about →

Code C/C++: Thuật toán Dijkstra tìm đường đi ngắn nhất

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng thuật toán Dijkstra.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Bai6.inp. 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (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  đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Bai6.inp"
void Doc_File(int A[max][max], int &n, int &D, int &C) {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Ma Tran Lien Ket Tuong Ung.\n";
cout<<D<<" "<<C<<endl;
for(int i =0;i<n;i++) {
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl; 
}
fclose(f);
D--; C--;
}
void Dijkstra(int A[max][max], int n, int D, int C) {
char DanhDau[max];
int Nhan[max], Truoc[max], XP, min;
for(int i=0; i<n; i++){
Nhan[i] = MAXINT;
DanhDau[i] = 0;
Truoc[i] = D;
}
Nhan[D] = 0;
DanhDau[D] = 1;
XP = D;
while(XP != C){
for(int j=0; j<n; j++)
if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
Nhan[j] = A[XP][j]+Nhan[XP];
Truoc[j] = XP;
}
min = MAXINT;
for(j = 0; j<n; j++)
if(min>Nhan[j]&& DanhDau[j]==0){
min = Nhan[j];
XP = j;
}
DanhDau[XP] = 1;
}
cout<<"Duong Di Ngan Nhat La:"<<Nhan[C]<<endl;
cout<<C+1<<" <-"<<Truoc[C]+1;
i = Truoc[C];
while(i!=D){
i = Truoc[i];
cout<<" <-"<<i+1;
}
}
void main() {
int A[max][max],n,Dau,Cuoi;



Doc_File(A,n,Dau,Cuoi);
Dijkstra(A,n,Dau,Cuoi);
getch();

} 
Kết quả chạy chương trình:

Tags: kỹ thuật lập trình, c, c++, toán rời rạc, đồ thị, tìm đường đi, Dijkstra.

More about →

Code C/C++: Tìm đường đi Euler của đồ thị (bài toán tìm đường đi)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán:sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.
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 Bai5.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: in ra màn hình đường đi qua tất cả các cạnh (nếu có)
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Bai5.inp"
int Dem = 0, SoCanh=0;  
int *L;    
int **A,n;
int XuatPhat=0;   
void Doc_File() {
int BacDinh;
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d",&n);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
BacDinh = 0;
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" "; 
if(A[i][j] == 1)
BacDinh++;
}
if(BacDinh%2==1)
XuatPhat = i;    
SoCanh+=BacDinh;
cout<<endl;
}
fclose(f);
SoCanh = SoCanh/2;      
L = new int [SoCanh+1]; 
L[0] = XuatPhat;
}
void InDuongDi() {
Dem++;
cout<<endl<<XuatPhat+1;
for (int i = 1; i<=SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int Canh) {
if(Canh > SoCanh)     
InDuongDi();
else {
for(int i = 0; i<n; i++)
if( A[L[Canh-1]][i]>0){
L[Canh] = i;
A[L[Canh-1]][i]=A[i][L[Canh-1]]=0;  
Try(Canh+1);       
A[L[Canh-1]][i]=A[i][L[Canh-1]]=1;  
L[Canh] = 0;
}
}
}
void main() {
Doc_File();
cout<<"\nDUONG DI";
Try(1);
if(Dem==0)
cout<<" KHONG CO";
delete*A,L;
getch();

} 
Kết quả chạy chương trình:

Tags: Kỹ thuật lập trình, toán rời rạc, c, c++, euler, đồ thị, tìm đường đi

More about →

Code C/C++: Đường đi Hamilton (bài toán đồ thị)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh xuất phát đi qua tất cả các đỉnh mỗi đỉnh chỉ qua duy nhất 1 lần.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách đánh dấu đỉnh đã đi qua trong quá trình tìm kiếm.
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 Bai4.inp
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng 2 ghi đỉnh xuất phát.
-  Dòng i+2 (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: in ra màn hình đường đi qua tất cả các đỉnh (nếu có).

Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai4.inp"
intDem = 0;     
int *L;      
char  *DanhDau;  
int**A,n,D;
//Đọc dữ liệu từ tập tin theo yêu cầu bài toán
void Doc_File() {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d",&n,&D);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--;
}
//Khởi tạo dữ liệu ban đầu cho bài toán
void KhoiTao() {
DanhDau = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
DanhDau[i] =0;  
L[i] = 0;
}
DanhDau[D] = 1;    
L[0] = D;
}
//Xuất đường đi ra màn hình
void InDuongDi(int Dinh) {
Dem++;
cout<<endl<<D+1;
for (int i = 1; i<Dinh; i++)
cout<<" -> "<<L[i]+1;
}
//Tìm kiếm đường đi
void Try(int Dinh){
if(Dinh == n) 
InDuongDi(Dinh);
else {
for(int i = 0; i<n; i++)
if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0){
L[Dinh] = i;
DanhDau[i] = 1;  
Try(Dinh+1);   
L[Dinh] = 0;
DanhDau[i] = 0; 
}
}
}
//Chương trình chính
void main() {
clrscr();
Doc_File();
KhoiTao();
cout<<"Duong di";
Try(1);
if(Dem==0)
cout<<" khong co.";
delete*A,DanhDau,L;
getch();

}
Kết quả chạy chương trình:

Tags: Kỹ thuật lập trình, c, c++, pascal, java, đồ thị, hamilton, tìm đường đi

More about →

Code C/C++: Tìm mọi đường đi từ giữa hai đỉnh của đồ thị

Tìm mọi đường đi từ giữa hai đỉnh
Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị liên thông và cho trong tập tin Bai3.inp 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (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 mọi đường đi từ đỉnh D đến C hay thông báo không tồn 
tại đường đi từ D đến C.
Mô tả:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai1a.inp"
intDem = 0;    
int *L;     
char  *DanhDau; 
int **A,n,D,C;
//Đọc dữ liệu từ tập tin
void Doc_File() { 
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C); 
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--; 
C--;
}
//Khởi tạo các biến ban đầu
void KhoiTao() {
DanhDau = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
DanhDau[i] = 0;
L[i] = 0;
}
DanhDau[D] = 1;    
L[0] = D;      
}
void InDuongDi(int SoCanh) {
Dem++;
cout<<endl<<D+1;
for (int i = 1; i<SoCanh; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int SoCanh) {
if(L[SoCanh-1] == C)    
InDuongDi(SoCanh);
else {
for(int i = 0; i<n; i++)
if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0 ){
L[SoCanh] = i;  
DanhDau[i] = 1; 
Try(SoCanh+1); 
L[SoCanh] = 0;
DanhDau[i]= 0;  
}
}
}
void main() {
Doc_File();
KhoiTao();
cout<<"Duong di tu "<<D+1<<" den "<<C+1;
Try(1);
if(Dem==0)
cout<<" khong co duong di";
delete*A,DanhDau,L;
getch();

}
Kết quả chạy chương trình:

Từ khóa: đường đi, đồ thị, đỉnh, c, c++, kỹ thuật lập trình, toán rời rạc, liên thông, tìm đường đi giữa 2 đỉnh của đồ thị

More about →

Code C/C++: Đếm số thành phần liên thông của đồ thị

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ố đỉ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 Bai2.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 chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define TenFile "Bai2.inp"
//Đọc dữ liệu từ file Bai2.inp
void Doc_File(int **A,int &n)  {
FILE*f = fopen(TenFile,"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);
}
//Hàm trả về số thành phần liên thông của đồ thị
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++)     
DanhDau[i] = 0;
do {
j = 0;
while(DanhDau[j]==1) 
j++;
DanhDau[j] = 1;   
Dem++;     
MLT++;      
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);     
return MLT;
}
//Chương trình chính
void main(){
clrscr();
int **A,n;
Doc_File(A,n);
cout<<"\nThanh phan lien thong: "<<TPLien_Thong(A,n);
delete *A;
getch();
}
Kết quả chạy chương trình:

Từ khóa: c, c++, toán rời rạc, liên thông, đồ thị, kỹ thuật lập trình, giải thuật, đếm thành phần liên thông của đồ thị

More about →