Tìm mọi đường đi từ đỉnh D đến C

Có n thành phố biết rằng đường đi giữa hai các thành phố (nếu có) là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận Anxn trong đó:
a. A[i,j] = 1 nếu có đường đi từ thành phố i đến thành phố j.
b. A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
c. A[i,j] = A[j,i].
Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu có).
Dữ liệu vào: cho trong file Bai2.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (0Dữ 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.
Ví dụ:
Input 1:
5
1 5
0 1 0 0 1
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
Output 1:
1->2->3->4->5
1->2->4->5
1->5
Input 2:
6
1 4
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
Output 2:
KHONG CO DUONG DI
Input 3:
5
1 5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
Output 3:
1->2->3->4->5
1->2->5
1->4->3->2->5
1->4->5
1->5
HƯỚNG DẪN THUẬT TOÁN
Sử dụng thuật toán tìm kiếm theo chiều sâu.
HƯỚNG DẪN CÀI ĐẶT
Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy.
- Các biến lưu trữ phải khai báo toàn cục, các biến lặp phải khai báo cục bộ.
- Trong thủ tục khởi tạo (void KhoiTao): khởi tạo mọi đỉnh chưa được đánh dấu, quá trình tìm kiếm xuất phát từ đỉnh D nên đánh dấu đỉnh D và lưu trữ đường đi xuất phát từ đỉnh D.
- Trong thủ tục tìm kiếm (void TimKiem): ta xuất phát tìm kiếm đỉnh tiếp theo dựa trên đỉnh lưu trữ trước đó để đảm bảo có đường đi (thoả tính liền kề của đồ thị). Nếu thoả mãn điều kiện đỉnh tìm kiếm trước đó bằng đỉnh C ta tiến hành xuất đường đi (đây là điều kiện đệ quy).

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileInt "Bai8.inp"
#define FileOut "Bai8.out"

/*Lưu lại những cạnh đã đi qua x->y*/
typedef struct Egde {
  int x,y;
};
/*Doc dữ liệu từ file*/
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 file*/
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);
}
/*Thuật toán Kruskal  */
void Kruskal(int **A, int n){
  char *D = new char[n];
  Egde *L = new Egde[n-1];
  int min, 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;
      }
      /*Tạo ra cây mới*/
      if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){
        T++;
        D[L[Dem].x] = D[L[Dem].y] = T;
      }
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0)
        D[L[Dem].x] = D[L[Dem].y];
      /*Đưa đỉnh tương ứng vào cây*/
      if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0)
        D[L[Dem].y] = D[L[Dem].x];
      /*Ghép 2 cây thành 1 cây mới*/
      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*/
void main() {
  int **A,n;
  Doc_File(A,n);
  Kruskal(A,n);
  delete *A;
}