#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <time.h>
#include <stack>
#include "DBL.h"
//#define NO_PATH_OUT // comment out this line for path output
void Error_Exit(const char *s);
typedef struct _Vertex {
dblStack S; // adj list contains edge index
int degree;
} Vertex;
typedef struct _Edge {
int v1, v2;
} Edge;
void graphGeneration(Vertex **V, Edge **E, int *VN, int *EN);
void adjListGenerate(Vertex *V, Edge *E, int VN, int EN);
void deallocGraph(Vertex *V, Edge *E, int VN);
int *Find_Euler(Vertex *V, Edge *E, int VN, int EN, int *flag, int *pathN);
DBList pool; // DBL storage pool
int main() {
int T, VN, EN;
Vertex *V;
Edge *E;
int *path; // Euler cycle or path
int pathN; // path length
int flag; // 0: cycle, 1: path, 2: none
clock_t start_time, finish_time;
scanf("%d", &T); // read # of tests
for (int t = 1; t <= T; t++) { // for each test
graphGeneration(&V, &E, &VN, &EN);
start_time = clock(); // set the start time
path = Find_Euler(V, E, VN, EN, &flag, &pathN); // find an Euler path or cycle
finish_time = clock(); // set finish time
double cmpt = (((double)(finish_time - start_time)) / CLK_TCK)*1000; // compute the time passed
printf("Test= %d flag= %d VnumInCycle/Path)= %d ", t, flag, pathN);
if (flag == 0)
printf("Euler_cycle(exec_time= %.2f msec)\n",cmpt);
else if (flag == 1)
printf("Euler_path(exec_time= %.2f msec)\n", cmpt);
else
printf("not_Eulerian(exec_time= %.2f msec)\n", cmpt);
#ifndef NO_PATH_OUT
if (flag != 2) {
for (int i = 0; i < EN + 1; i++) {
printf("%d\n", path[i]);
}
}
#endif
if (flag != 2)
delete[] path;
deallocGraph(V, E, VN);
}
pool.freeDBL_pool(); // clear all the DBL elements
return 0;
}
int *Find_Euler(Vertex *V, Edge *E, int VN, int EN, int *flag, int *pathN) {
// input V, VN, E, EN
// output through paramters
// *flag = 0 (Euler cycle), 1 (Euler path), 2 (not Eulerian)
// *pathN = size of path[] array(path의 길이)
// output by return
// *path = list of vertex ids found(Euler cycle or path)
stack<int> ST; // use STL stack as explained in the class
int *path = NULL;
// *** 이 부분을 작성하세요
int *numOfV = new int[VN];
DBL* cur; DBL* twins;
path = new int[EN+1];
int** mat;
mat = new int* [VN];
for (int i = 0; i < VN; i++) {
mat[i] = new int [V[i].degree];
}
for (int i = 0; i < VN; i++) {
cur = V[i].S.top();
// printf("degree %d\n", _msize(mat[i])/sizeof(*mat));
for (int j = 0; j < _msize(mat[i]) / sizeof(*mat); j++) {
mat[i][j] = cur->d;
cur = cur->rp;
// printf("%d ", mat[i][j]);
}
// printf("\n");
}
//*pathN = 0;
//만일 전부 짝수라면 오일러사이클 - 임의의 짝수에서 시작
//만일 하나라도 홀수 - 오일러패스 - 이 홀수부터 시작
//만일 홀수인 정점이 홀수개 - 아무것도 아님.
*flag = 0; int start=0;
for (int i = 0; i < VN; i++) {
if (V[i].degree % 2 != 0) {
*flag = 1; //하나라도 홀수이니, 오일러패스
start = i; //이 홀수인 점부터 시작
break;
}
}
ST.push(start);
int vx; int idx = 0;
int wx; int dlt;
int length = 0;
while (!ST.empty()) {
vx = ST.top();
// printf("\n\nvx %d size %d\n\n", vx, ST.size());
if (V[vx].degree == 0) {
path[idx] = vx;
idx++;
// printf("pop %d\n", vx);
length++;
ST.pop();
}
else {
cur = V[vx].S.top();
//cur이 널포인터.
// printf("cur %d twin %d\n\n", cur->d, cur->twin->d);
twins = cur->twin;
wx = cur->d;
dlt = twins->d;
//에지 e를 그래프에서 제거 후 s.push(w), twin이용해 양쪽다제거
//이때, 제거되는 twin은 해당 리스트가 존재하는 v의 스택에서 꺼내와야 함
//에지 자체의 정보를 찾으면 됨
// printf("dlt %d's top %d\n", dlt, V[dlt].S.top()->d);
// printf("cur %d's top %d\n", wx, V[wx].S.top()->d);
// printf("wx %d dlt %d vx %d\n", wx, dlt, vx);
V[wx].S.remove(twins);
V[dlt].S.remove(cur);
DBL* now;
V[dlt].degree--;
V[wx].degree--;
// for (int i = 0; i < VN; i++) {
// now = V[i].S.top();
// while (now != NULL) {
// printf("%d ", now->d);
// now = now->rp;
// }
// printf("\n");
// printf("%d ", V[i].degree);
// }
// printf("\n");
ST.push(wx);
}
// for (int j = 0; j < sizeof(path) / sizeof(int); j++)
// printf("%d ", path[j]);
// printf("\n");
}
if (length < EN + 2)
*pathN = _msize(path) / sizeof(path);
else
*pathN = 0;
//path순서대로, 각 mat에 해당 요소가 있는지 없는지 구별
int qijun = 0;
bool excepT = false;
for (int i = 0; i < *pathN - 1; i++) {
int starter = path[i+1];
// printf("start %d\n", starter);
for (int j = 0; j < _msize(mat[path[i]]) / sizeof(*mat); j++) {
qijun = mat[path[i]][j];
// printf("qijun %d\n", qijun);
//만일 다음 요소가 mat[i] 내에 있다면, 다음으로
if (starter == qijun)
break;
//없다면 여기로 오겠지. 그렇다면 아예 나가
if(j+1 == _msize(mat[path[i]]) / sizeof(*mat)) {
// printf("fase");
excepT = true;
*flag = 2;
break;
}
}
if (excepT == true) {
*pathN = 0;
break;
}
}
free(mat);
return path;
}
void deallocGraph(Vertex *V, Edge *E, int VN) {
DBL *p;
// *** 여기에 adj list를 삭제하는 routine을 작성하세요
for (int i = 0; i < VN; i++) {
while (!(V[i].S.empty())) {
p = V[i].S.top();
pool.freeDBL(p);
}
}
delete[] V;
delete[] E;
}
void graphGeneration(Vertex **V, Edge **E, int *VN, int *EN) {
scanf("%d %d", VN, EN); // read # of vertices and edges
//allocVandEarray(V, E, *VN, *EN); // vertex and edge array allocation
*V = new Vertex[*VN];
*E = new Edge[*EN];
if (*V == NULL || *E == NULL) {
Error_Exit("Memory Allocation Error!");
}
for (int v = 0; v < *VN; v++) {
(*V)[v].degree = 0;
}
//정점의 수만큼 실행
//0, 1이 입력: e번째 엣지의 v1(시작점)과 v2(도착점)을 입력받음
//해당 시작점과 도착점은 디그리가 증가함
for (int e = 0; e < *EN; e++) {
scanf("%d %d", &((*E)[e].v1), &((*E)[e].v2)); // read edge information
++((*V)[(*E)[e].v1].degree);
++((*V)[(*E)[e].v2].degree);
}
adjListGenerate(*V, *E, *VN, *EN); // create adj lust in G=(V,E)
}
//그럼 그 리스트를 만든다
//엣지와 정점은 전부 관련 배열에서 관리되고 있음
void adjListGenerate(Vertex *V, Edge *E, int VN, int EN) {
// Construct adjacent list in V array
int v1, v2;
DBL *adjE1, *adjE2;
// *** 이 부분을 작성하세요
for (int i = 0; i < EN; i++) {
v1 = E[i].v1;
v2 = E[i].v2;
adjE1 = pool.allocDBL(); adjE2 = pool.allocDBL();
adjE1->twin = adjE2; adjE2->twin = adjE1;
adjE1->d = v1; adjE2->d = v2;
V[v1].S.push(adjE2);
V[v2].S.push(adjE1);
// printf("%d %d\n", v1, v2);
}
DBL* cur;
for (int i = 0; i < VN; i++) {
cur = V[i].S.top();
while (cur != NULL) {
// printf("%d ", cur->d);
cur = cur->rp;
}
// printf("\n");
}
// printf("\n");
}
void Error_Exit(const char *s) {
printf("%s", s);
exit(-1);
}
DBL *DBList::allocDBL(void) { // allocate a DBL element
DBL *p;
// *** 이 부분을 작성하세요
if (DBL_pool == NULL) {
p = (DBL*)malloc(sizeof(DBL));
if (p == NULL)
Error_Exit("Memory alloc error(alloc_DBL).");;
UsedMemoryForDBLs += sizeof(DBL);
p->d = NONE;
}
else {
p = DBL_pool; //pool- 스택 그자체. 즉, 첫번째요소
DBL_pool = p->rp; //p:새로 생성한 노드. 이를 첫번째로 하고,
}
p->rp = p->lp = p->twin = NULL; //포인터 클리어
++DBL_cnt;
return(p);
}
void DBList::freeDBL(DBL *p) {
// move p to pool
if (p->d == NONE) {
Error_Exit("This element is already freed(Free_DBL).");
}
// *** 이 부분을 작성하세요
p->d = NONE;
p->rp = DBL_pool;
DBL_pool = p;
--DBL_cnt; // reduce # of active DBL elements by one
}
void DBList::freeDBL_pool(void) {
DBL *p = DBL_pool;
while (p != NULL) {
DBL_pool = p->rp; // get next pointer
delete p;
p = DBL_pool;
UsedMemoryForDBLs -= sizeof(DBL);
}
if (DBL_cnt != 0) {
Error_Exit("Non-zero DBL_cnt after cleanup.");
}
}
void dblStack::push(DBL *p) {
// *** 이 부분을 작성하세요
if (ST != NULL) {
ST->lp = p; //link left pointer if Q!=NULL
}
p->rp = ST;
p->lp = NULL;
ST = p;
}
DBL *dblStack::pop(void) { // remove and return p in front of Q
DBL *p;
// *** 이 부분을 작성하세요
p = ST;
if (ST->rp == NULL)
ST = NULL;
else {
ST = ST->rp;
ST->lp = NULL;
}
return p;
}
void dblStack::remove(DBL *p) { // delete p from ST
// printf("who is top %d and %d\n", p->d, ST->d);
// *** 이 부분을 작성하세요
if (ST == p) { //p가 스택의 첫 요소일 때
ST = p->rp; //그 오른쪽을 맨 처음으로 놓고
if (p->rp != NULL) { //그게 널이라면
(p->rp)->lp = NULL; //그 우의 좌표(원래 첫 요소)를 널로
}
}
else { //그게 아니라면
(p->lp)->rp = p->rp; //p의 왼쪽의 오른쪽과 p의 오른쪽을 링크
if (p->rp != NULL) { //p의 오른쪽이 널이 아니라면
(p->rp)->lp = p->lp; //p의 오른쪽의 왼쪽과 p의 왼쪽을 링크
}
}
}
DBL *dblStack::top(void) {
return ST;
}
bool dblStack::empty(void) {
if (ST == NULL)
return true;
else
return false;
}