ccs

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>


using namespace std;
#define MAX 100
struct DOTHI
{
	int soDinh; // SO DINH CUA DO THI
	int trongSo[MAX][MAX]; // TRONG SO CUA MA TRAN DO THI
	char tenDinh[MAX]; // TEN CUA DINH
};

//===================       MENU     ============================
void showMenu()
{
	printf("\n********************* MENU *********************");
	printf("\n1. Duong Di Euler ");
	printf("\n2.");
	printf("\n0. Thoat");
	printf("\n************************************************");
}

void showMenuEuler()
{
	printf("\n***************** Euler's Menu *****************");
	printf("\n\n1. Kiem tra Do Thi VO HUONG hay CO HUONG ");
	printf("\n2. Kiem tra so thanh phan lien thong ");
	printf("\n3. Dem so bac cua dinh X ");
	printf("\n4. Dem so bac cua tat ca cac dinh  ");
	printf("\n5. Kiem tra Euler  ");
	printf("\n0. Tro ve Menu chinh");
	printf("\n\n************************************************");
}

//============== DOC DU LIEU DO THI TU FILE =====================
int docDuLieuTuFile(DOTHI& g, char* fileName)
{
	FILE* f = fopen(fileName, "rt");
	if (f == NULL) {
		printf("Khong mo duoc file!  ");
		return -1;//Doc file khong thanh cong
	}

	fscanf(f, "%d\n", &g.soDinh);
	for (int i = 0; i < g.soDinh; i++)
	{
		fscanf(f, "%c ", &g.tenDinh[i]);
	}

	// doc trong so cua ma tran
	for (int i = 0; i < g.soDinh; i++)
	{
		for (int j = 0; j < g.soDinh; j++)
		{
			fscanf(f, "%d", &g.trongSo[i][j]);
		}
	}
	fclose(f);
	return 0;//Doc file thanh cong
}

//============== IN MA TRAN DO THI RA MAN HINH ==================
void printMatrix(DOTHI g)
{
	printf("\t");
	for (int i = 0; i < g.soDinh; i++)
	{
		printf("%3c", g.tenDinh[i]);
	}
	printf("\n\n");

	for (int i = 0; i < g.soDinh; i++)
	{
		printf(" %c\t", g.tenDinh[i]);
		for (int j = 0; j < g.soDinh; j++)
		{
			printf("%3d", g.trongSo[i][j]);
		}
		printf("\n");
	}
}

// TRẢ VỀ INDEX CỦA ĐỈNH ĐƯỢC TRUYỀN VÀO
int getIndexDinh(DOTHI g, char tenDinh)
{
	int indexDinh = -1;
	for (int i = 0; i < g.soDinh; i++)
	{
		if (g.tenDinh[i] == tenDinh)
		{
			indexDinh = i;
			break;
		}
	}
	return indexDinh;
}

//==================          DANH       =========================

int CheckVoHuong(DOTHI g)// Trả về 1 khi VÔ HƯỚNG và 0 khi CÓ HƯỚNG
{
	for (int i = 0; i < g.soDinh - 1; i++)
		for (int j = i + 1; j < g.soDinh; j++)
		{
			if (g.trongSo[i][j] != g.trongSo[j][i])
				return 0;// Đồ thị Có Hướng 
			else
				return 1;// Đồ thị Vô Hướng
		}
}

void NhapTenFile(DOTHI g, char* fileName)
{
	do
	{
		if (docDuLieuTuFile(g, fileName) != 0)
			cout << "\n\nTen File khong dung luu long nhap lai !\n";
		cout << "\nNhap ten File do thi : ";
		cin >> fileName;
	} while (docDuLieuTuFile(g, fileName) != 0);
}
void printfCheckVoHuong(DOTHI g, char* fileName)
{
	NhapTenFile(g, fileName);
	docDuLieuTuFile(g, fileName);
	cout << "\n\n";
	printMatrix(g);
	int tmp = CheckVoHuong(g);
	if (tmp == 1)
		cout << "\n\n\tDo Thi VO HUONG ";
	if (tmp == 0)
		cout << "\n\n\tDo Thi CO HUONG ";
	cout << "\n\n\n";
}

void SearchDLT(int X, DOTHI g, int LT[])
{
	for (int i = 0; i < g.soDinh; i++)
	{
		if (g.trongSo[i][X] && LT[i] == 0)
		{
			LT[i] = LT[X];
			SearchDLT(i, g, LT);
		}
	}
}

int SearchSoTPLT(DOTHI g)
{
	int LT[MAX] = { 0 };
	int SoTPLT = 0;
	for (int i = 0; i < g.soDinh; i++)
	{
		if (LT[i] == 0)
		{
			SoTPLT++;
			LT[i] = SoTPLT;
			SearchDLT(i, g, LT);
		}
	}
	return SoTPLT;
}

void printfSoTPLT(DOTHI g, char* fileName)
{
	NhapTenFile(g, fileName);
	docDuLieuTuFile(g, fileName);
	cout << "\n\n";
	printMatrix(g);
	if (SearchSoTPLT(g) > 0 && SearchSoTPLT(g) < 998)
	{
		cout << "\n\nSo thanh phan lien thong cua Do Thi la:" << SearchSoTPLT(g);
		cout << "\n\n\n";
	}
}

int SearchSoBacDinh(DOTHI g, int DinhX)
{
	int sumBac = 0;
	for (int i = 0; i < g.soDinh; i++)
	{
		if (g.trongSo[DinhX][i] != 0)
			sumBac++;
	}
	return sumBac;
}

int ChuyenChuThanhSo(DOTHI g, char DinhXC)
{
	for (int i = 0; i < g.soDinh; i++)
	{
		if (g.tenDinh[i] == DinhXC)
			return i;
	}
	return -1;
}

char ChuyenSoThanhChu(DOTHI g, int DinhX)
{
	if (DinhX >= 0 && DinhX < g.soDinh)
	{
		return g.tenDinh[DinhX];
	}
}

void printfSoBacDinhX(DOTHI g, char* fileName)
{
	NhapTenFile(g, fileName);
	char DinhXC;
	int DinhX;
	docDuLieuTuFile(g, fileName);
	cout << "\n\n";
	printMatrix(g);
	do
	{
		cout << "\n\nNhap ten dinh can tim: ";
		cin >> DinhXC;
		{
			if (ChuyenChuThanhSo(g, DinhXC) == -1)
				cout << "\nTen Dinh khong dung vui long nhap lai !";
		}
	} while (ChuyenChuThanhSo(g, DinhXC) == -1);
	DinhX = ChuyenChuThanhSo(g, DinhXC);
	cout << "\n\nSo Bac cua dinh " << DinhXC << " la :" << SearchSoBacDinh(g, DinhX);
}

void printfSoBacCacDinh(DOTHI g, char* fileName)
{
	NhapTenFile(g, fileName);
	docDuLieuTuFile(g, fileName);
	cout << "\n\n";
	printMatrix(g);
	cout << "\n\t   SO BAC CUA DINH :";
	for (int i = 0; i < g.soDinh; i++)
		cout << "\n\tSo Bac cua dinh " << g.tenDinh[i] << " la :" << SearchSoBacDinh(g, i);
}

int CheckEuler(DOTHI g)// return 0 = Chu Trinh || return 1 = Đường đi || return 2 = Không phải đồ thị Euler
{
	int VoHuong = CheckVoHuong(g);
	int SoTPLT = SearchSoTPLT(g);
	int SoBacLe = 0;
	for (int i = 0; i < g.soDinh; i++)
	{
		if (SearchSoBacDinh(g, i) % 2 == 0)
			SoBacLe++;
	}
	if (VoHuong == 1 && SoTPLT == 1 && SoBacLe == 0)
		return 0;//Chu trình Euler
	if (VoHuong == 1 && SoTPLT == 1 && SoBacLe == 2)
		return 1;//Đường đi Euler
	return 2;// Không phai Euler

}

void SearchDD(DOTHI &g, int X, int LKDD[], int& sl)
{
	for (int i = 0; i < g.soDinh; i++)
		if (g.trongSo[X][i] != 0)
		{
			g.trongSo[X][i] = g.trongSo[i][X] = 0;
			SearchDD(g, i, LKDD, sl);
		}
	LKDD[sl++] = X;
}

void printfLKDDEuler(DOTHI &g, char* fileName)
{
	NhapTenFile(g, fileName);
	docDuLieuTuFile(g, fileName);
	int Euler = CheckEuler(g);
	char DinhXC;
	int DinhBD;
	cout << "\n\n";
	printMatrix(g);
	if (Euler == 2)
	{
		cout << "\n\nDo thi khong phai Euler.";
		return;
	}
	if (Euler == 0)
	{
		cout << "\n\nChon dinh Bat Dau cua Chu Trinh Euler: ";
		cin >> DinhXC;
		DinhBD = ChuyenChuThanhSo(g, DinhXC);
	}
	if (Euler == 1)
	{
		for (int i = 0; i < g.soDinh; i++)
		{
			if (SearchSoBacDinh(g, i) % 2)
			{
				DinhBD = i;
				break;
			}
		}
	}
	int LKDD[MAX];
	int sl=0;
	SearchDD(g, DinhBD, LKDD, sl);
	if (Euler == 0)
		cout << "\n\t Chu Trinh Euler la : ";
	if (Euler == 1)
		cout << "\n\t Duong di Euler la : ";
	for (int i = sl - 1; i >= 0; i--)
	{
		cout << g.tenDinh[ChuyenSoThanhChu(g, LKDD[i])];
	}
}
//================================================================


//==================          MINH       =========================

//================================================================


//==================          Hòa        =========================

//================================================================


//==================       ANH PHONG      ========================

//================================================================
void main()
{
	DOTHI g;
	char fileName[100] = "data.txt";
	int luaChon, luachonEuler;
	do
	{
		system("cls"); // xóa màn hình console
		showMenu();
		printf("\nNhap vao lua chon: ");
		scanf("%d", &luaChon);
		switch (luaChon)
		{
		case 1:
			do
			{
				system("cls"); // xóa màn hình console
				showMenuEuler();
				printf("\nNhap vao lua chon: ");
				scanf("%d", &luachonEuler);

				switch (luachonEuler)
				{
				case 1:
					printfCheckVoHuong(g, fileName);
					_getch();
					break;
				case 2:
					printfSoTPLT(g, fileName);
					_getch();
					break;
				case 3:
					printfSoBacDinhX(g, fileName);
					_getch();
					break;
				case 4:
					printfSoBacCacDinh(g, fileName);
					_getch();
					break;
				case 5:
					printfLKDDEuler(g, fileName);
					_getch();
					break;
				case 0:
					printf("\nTro ve Menu chinh!");
					break;
				default:
					printf("\nVui long nhap lai");
					_getch();
					break;
				}
			} while (luachonEuler != 0);
			break;
		case 2:
		{
			printMatrix(g);
			_getch();
			break;
		}
		case 0:
			printf("\nOut success!");
			_getch();
			return;
		default:
			printf("\nVui long nhap lai");
			_getch();
			break;
		}
	} while (1);

}