//Do thi lien thong
#include <stdio.h>
#include <conio.h>
#define MAX 100
#define input “g:/test2.txt”
typedef struct graph{
int n;
int a[MAX][MAX];
}DOTHI;
int DocDoThi(char text[MAX],DOTHI &g){
FILE *f;
f=fopen(text,”rt”);
if(f == NULL){
printf(“\n Khong tim duoc file”);
return 0;
}
fscanf(f,”%d”,&g.n);
for(int i=0; i<g.n;i++){
for(int j=0;j<g.n;j++)
fscanf(f,”%d”,&g.a[i][j]);
}
fclose(f);
return 1;
}
void XuatDoThi(DOTHI g){
printf(“\n So dinh cua ma tran la: %d”,g.n);
printf(“\n Ma Tran: \n”);
for(int i=0;i<g.n;i++){
printf(“\t”);
for(int j=0;j<g.n;j++)
printf(“%d “,g.a[i][j]);
printf(“\n”);
}
}
void DiTimCacDinhLienThong(DOTHI g, int nhan[MAX], int i){
for(int j=0;j<g.n;j++){
if(g.a[i][j] != 0 && nhan[j] != nhan[i]){
nhan[j]=nhan[i];
DiTimCacDinhLienThong(g,nhan,j);
}
}
}
void XetLienThong(DOTHI g){
int Nhan[MAX];
int i;
for(i=0;i<g.n;i++)
Nhan[i] = 0;
int SoThanhPhanLT = 0;
for(i=0;i<g.n;i++){
if(Nhan[i] == 0){
SoThanhPhanLT ++;
Nhan[i] = SoThanhPhanLT;
}
if(Nhan[i] != 0)
DiTimCacDinhLienThong(g,Nhan,i);
}
printf(“So thanh phan lien thong la %d\n”,SoThanhPhanLT);
for(i=1; i<=SoThanhPhanLT; i++){
printf(“Thanh phan lien thong thu %d gom cac dinh: “,i);
for(int j=0; j<g.n;j++){
if(Nhan[j]==i)
printf(“%d “,j);
}
printf(“\n”);
}
}
int main(){
DOTHI g;
if(DocDoThi(input,g) == 1){
printf(“\n Do thi doc thanh cong…”);
XuatDoThi(g);
printf(“Bam 1 phim bat ki de bat dau xet tinh lien thong cua do thi…\n\n”);
getch();
XetLienThong(g);
}
getch();
} |
