DFS

//Bai toan: Cho do thi G(V, E).
// 1. Cho biet do thi co lien thong khong
// 2. Neu do thi lien thong: Tim duong di dai nhat tu u0 den v0
//
//Algorithm: Deapth First Search
//Data structure: Ma tran ke
//Input: Text file
//Output: Text file
//
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <iomanip.h>
//
#define    MAX    100
#define FINPUT    "DFS2.INP"
#define FOUTPUT    "DFS2.OUT"
//
int n,u0,v0;
int a[MAX][MAX];
//
void nhapdulieu(){
  int i,j,x;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++) a[i][j]=0;
  i=1;
  ifstream fin(FINPUT);
  fin>>n>>u0>>v0;
  while (!fin.eof()){
    fin>>j;
    if (j==0) i++;
    else {a[i][j]=1; a[j][i]=1;}
  }
  fin.close();
  cout<<n<<", "<<u0<<", "<<v0<<endl;
  for(i=1;i<=n;i++) {
    cout<<i<<": ";
    for(j=1;j<=n;j++)
    if(a[i][j]>0) cout<<j<<",";
    cout<<endl;
  }
}
//
int pred[MAX];
//
void DFS(int u){
 int v;
 for(v=1;v<=n;v++)
 if(a[u][v]==1 && pred[v]==0)
 { pred[v]=u;
   DFS(v);
 }
}
//
int path[MAX];
int lt,m;
//
void xuli(){
 int u;
 lt=1;
 for(u=1;u<=n;u++) pred[u]=0;
 pred[u0]=-1;
 DFS(u0);
 for(u=1;u<=n;u++)
 if (pred[u]==0) lt=0;
 if (lt) {
   m=0;
   u=v0;
   do{
     path[++m]=u;
     u=pred[u];
   }while (u!=-1);
 }
}
//
void xuatketqua(){
 ofstream fo(FOUTPUT);
 if(!lt) fo<<"Do thi khong lien thong";
 else{ fo<<"Duong di dai nhat can tim co do dai "<<m<<endl;
       for(int i=m;i>0;i--)
      fo<<path[i]<<"->";
     }
 fo.close();
}
//
int main(){
 clrscr();
 nhapdulieu();
 xuli();
 xuatketqua();
 cout<<"done!"; getch();
 return 0;
}
=====================
9 1 8
2 0
3 9 0
5 7 8 0
5 7 0
6 8 0
7 0
9 0
9 0