Depth-first search

#include "fstream"
#include "iostream"

using namespace std;

int Arr[100][100];         // Ma trận kề
int size; // Số đỉng
int visited[100] = {0}; // Tạo mảng đánh dấu các phần tử đã duyệt

// Nhập file từ ma trận kề
void Import(char *filename)
{
ifstream txt (filename);
txt >> size;
if (txt.is_open())
{
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt >> Arr[i][j];
}
}
txt.close();
}
else cout << "Unable to open file"; 
}

// Xuất file từ ma trận kề
void Export()
{
ofstream txt ("Output.txt");
if (txt.is_open())
{
txt << size << "\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt << Arr[i][j];
if(j != size-1)
txt << " ";
}
if (i != size-1)
txt << "\n";
}
txt.close();
}
else cout << "Unable to open file";
}

void DFS(int v, int dem)   // Deep First Search
{
visited[v] = dem;      // Đánh dấu vị trí đã duyệt

int i = 0;
for (i = 0; i < size; ++i)    // Tiếp tục xét các cạnh kề
{
bool kt = (Arr[v][i] == 1 || Arr[i][v] == 1);  // có cạnh nối hay không
if (kt && visited[i] == 0)    // Nếu có cạnh nối và đỉnh đó chưa thăm
{
DFS(i, dem);  // Xét tiếp cạnh tiếp theo
}
}
}

int xetLienThong()
{
int dem = 0; // biến để đếm xem có bao nhiêu thành phần liên thông

for (int i = 0; i < size; i++)   // Xét mảng visited
{
if (visited[i] == 0)         // Nếu duyệt đến phần tử nào
{
dem++;
DFS(i, dem);  // thì duyệt theo hướng đó
}
}

return dem;
}

void InThanhPhanLienThong()
{
int soTPLT = xetLienThong();

if(soTPLT == 1)
printf("Do thi lien thong.\n");
else
{
printf("Do thi khong lien thong, co %d TPLT.\n", soTPLT);
for(int i = 1; i <= soTPLT; ++i)
{
printf("Mien lien thong %d:", i);
for(int j = 0; j < size; ++j)
{
if(visited[j] == i)
printf(" %d", j);
}
printf("\n");
}
}
}

void main()
{
Import("Matrix.txt");
Export();
InThanhPhanLienThong();
}