#include <iostream>
#include <stdio.h>
#include <conio.h>
char stack[20]; //them phan tu vao Stack
int dinh = -1, n; //luu dinh (top) da di qua
char b[20], duongdi_ketthuc[20]; //i
char ma_tranke[20][20]; //A(ij)
int fp = 0, count; //dinh xuat phat la dinh bac le neu do thi co dinh bac le
FILE * fo, * fi;
//day hoat dong vao trong stack(phan tu tren cung cua stack)
void them_vao(char gia_tri)
{
dinh = dinh + 1;
stack[dinh] = gia_tri;
}
//lay hoat dong ra tu stack(phan tu tren dinh cua Stack)
char lay_ra()
{
return stack[dinh--];
}
//kiem tra tat ca cac dinh lien ke ben ngoai/cac nut da di qua
//hoac khong co
int daqua_tatca(int i)// bieu dien bang ma tran dinh-dinh co hoac khong
{
int j;
for (j = 0; j<n; j++)
{
if (ma_tranke[i][j] == 'c')
return 0;
}
return 1;
}
//cho biet den cac chi so cua nut hien hanh trong mang b tai cac nut
int chobiet_khong(char k)
{
int l = 0;
while (k != b[l])
l++;
return l;
}
//hien thi duong di/chu trinh euler
void duong_ht()
{
int i;
for (i = 0; i<fp; i++)
{
printf("%c ->", duongdi_ketthuc[i]);
}
}
//tim kiem chu trinh/duong di euler va su luu lai no trong mang[] duong di ket thuc
void tim_euler(int goc)
{
int l, j;
//day goc vao trong stack
them_vao(b[goc]);
//tien trinh len den kho chua tro nen rong v.e(G) dinh=-1
while (dinh != -1)
{
//cho biet chi so mang cua dinh nam o stack
l = chobiet_khong(stack[dinh]);
// neu tat ca cac nut lien ke da di qua
// lay phan tu tu stack ra va su luu lai no trong mang[] duong di ket thuc
if (daqua_tatca(l))
{
duongdi_ketthuc[fp++] = lay_ra();
}
// neu bat ki nut nao chua di qua co the su dung nut do them vo trong stakc
//dau vet canh(Edge(ij)-noi 2 dinh) do nhu da di qua boi danh dau 'k' trong ma tran ke[][]
// pha vo cac vong lap(thuc hien lap)
else
{
for (j = 0; j<n; j++)
{
if (ma_tranke[l][j] == 'c')
{
ma_tranke[l][j] = 'k';
ma_tranke[j][l] = 'k';
them_vao(b[j]);
break;
}
}
}
}
}
//cho biet den bac dinh cua nut v.e(G) khong co cac canh hien thoi da ket noi den nut
int chobiet_bacdinh(int i)
{
int j, deg_bac = 0;
for (j = 0; j<n; j++)
{
if (ma_tranke[i][j] == 'c') deg_bac++;
}
return deg_bac;
}
//gan gia tri goc cua do thi
//dieu kien 1: Neu tat ca cac nut co bang bac dinh chan, nen tai do se la mot mach/chu trinh euler
//chung ta co the bat dau duong di tu nut bat ki
//dieu kien 2: Neu chinh xa la 2 dinh bac le, nen tai do se la mot duong di euler
//chung ta co the bat dau tu nut nao co dinh bac le
//dieu kien 3: neu cac nut hon 2 hoac chinh xac la 1 nut dinh bac le, khong la duong di/chu trinh euler
//tim_goc se quay lai 0 neu khong la duong di/chu trinh euler
//mat khac no se quay lai chi so mang cua nut bat ki nhu goc
int tim_goc()
{
int i, cur = 1;// gia dinh goc la 1
for (i = 0; i<n; i++)
{
if (chobiet_bacdinh(i) % 2 != 0)
{
count++;
cur = i;// su luu lai nut co lua chon dinh bac le den bien cur
}
}
// neu dem khong chinh xac la 2 khi khong la duong di/chu trinh euler vi the quay lai 0
if (count != 0 && count != 2)
{
return 0;
}
else return cur;// neu cac nut chinh xac la 2 dinh bac le, no se quay lai nhu 1 nut goc mat khac quay lai 1 nhu da gia dinh o goc
}
void dfs(int start, int m) {
if (m < 1) {
fprintf(fo, "%c", duongdi_ketthuc[0]);
for (int i = 1; i < fp; ++i)
fprintf(fo, " -> %c", duongdi_ketthuc[i]);
fprintf(fo, "\n");
}
else
for (int i = 0; i < n; ++i)
if (ma_tranke[start][i] == 'c') {
ma_tranke[start][i] = ma_tranke[i][start] = 'k';
duongdi_ketthuc[fp++] = b[i];
dfs(i, m - 1);
ma_tranke[start][i] = ma_tranke[i][start] = 'c';
--fp;
}
}
void all_Eulerian_paths(int goc) {
int m = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (ma_tranke[i][j] == 'c')
++m;
duongdi_ketthuc[0] = b[goc];
fp = 1;
dfs(goc, m);
}
int main()
{
fi = fopen("graph.txt", "r"); // thay thế tên input file mà bạn muốn.
fscanf(fi, "%d\n", &n);
for (int i = 0; i < n; ++i)
fscanf(fi, "%c ", &b[i]);
char temp;
for (int i = 0; i < n; ++i) {
fscanf(fi, "%c ", &temp);
for (int j = 0; j < n; ++j)
fscanf(fi, "%c ", &ma_tranke[i][j]);
}
fclose(fi);
fo = fopen("graph_out.txt", "w"); // thay thế tên output file mà bạn muốn.
// tim_goc se quay lai 0 neu khong la duong di/chu trinh euler
// mat khac no se quay lai chi so mang cua nut bat ki nhu goc
int goc1;
if (goc1 = tim_goc())
{
if (count) fprintf(fo, "la duong di euler\n");
else fprintf(fo, "la chu trinh euler\n");
all_Eulerian_paths(goc1);
//tim_euler(goc1);
//duong_ht();
}
else fprintf(fo, "khong la duong di hoac chu trinh euler\n");
fclose(fo);
getch();
}