20191102

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAX 100

struct Node
{
	char name;
	int idx;
	int nextIdx[MAX];
	int linkedNum = 0;
};

struct Stack
{
	int top;
	int bottom;
	Node data[MAX];
};

struct Graph
{
	Node vertex[MAX];	
	int visitCheck[MAX];
	int size;
}graph;


void initStack(Stack *s)
{
	s->top = 0;
	s->bottom = 0;
}

void push(Stack *s, Node node)
{
	s->data[s->top] = node;
	s->top++;
}

void pop(Stack *s)
{
	s->top--;
}

void findPathActivity(Stack *pathStack, Node sNode, Node vNode, Node eNode)
{
	
	if(vNode.idx == eNode.idx) { 
		printf("!destination!\n");
		push(pathStack, vNode);
		graph.visitCheck[vNode.idx] = 1;
		return; 
	}
	if(graph.visitCheck[vNode.idx] == 1) { 
		printf("!circulation!\n");
		return; 
	}
	
	push(pathStack, vNode);
	graph.visitCheck[vNode.idx] = 1;
	
	for(int i=0; i<vNode.linkedNum; i++){
		printf("[current node : %c, idx : %d\n", vNode.name, vNode.idx);
		printf("next node : %c, idx : %d]\n\n", graph.vertex[vNode.nextIdx[i]].name, graph.vertex[vNode.nextIdx[i]].idx);
		findPathActivity(pathStack, sNode, graph.vertex[vNode.nextIdx[i]], eNode);
		if(vNode.idx == sNode.idx)
		{
			if(i+1 == vNode.linkedNum)return;
			printf("!new path!\n");
			for(int i=0; i<graph.size; i++){
				graph.visitCheck[i] = 0;
			}
		}
		pop(pathStack);
	}
}

void findPath(Node sNode, Node eNode)
{
	Stack pathStack;
	initStack(&pathStack);
	
	Node visitNode = sNode;
	findPathActivity(&pathStack, sNode, sNode, eNode);
}

int main()
{
	freopen("input.txt","r",stdin);
	int graphSize;
	char verName[MAX];
	int adjMatrix[MAX][MAX] = {0};
	
	scanf("%d", &graphSize);
	
	graph.size = graphSize;
	
	for(int i=0;i<graphSize; i++){
		scanf(" %c", &verName[i]);
	}
	
	int g_cnt = 0;
	for(int i=0; i<graphSize; i++){
		int cnt = 0;
		Node tempNode;
		tempNode.name = verName[i];
		tempNode.idx = i;
		for(int j=0; j<graphSize; j++){
			scanf("%d", &adjMatrix[i][j]);
			if(adjMatrix[i][j] == 1){
				tempNode.nextIdx[cnt++] = j;	
			}
		}
		tempNode.linkedNum = cnt;
		graph.vertex[g_cnt++] = tempNode;
	}
	
	for(int i=0; i<graphSize; i++){
		printf("%c : ", verName[i]);
		for(int j=0; j<graph.vertex[i].linkedNum; j++){
			printf("-> %c ", verName[graph.vertex[i].nextIdx[j]]);
		}
		printf("\n");
	}
	printf("==============================\n");
	/*========================*/
	
	char sVertex;
	char eVertex;
	Node sNode, eNode;
	scanf(" %c %c", &sVertex, &eVertex);
	for(int i=0; i<graphSize; i++){
		if(verName[i] == sVertex){
			sNode = graph.vertex[i];
		}
		if(verName[i] == eVertex){
			eNode = graph.vertex[i];
		}
	}
	findPath(sNode, eNode);
	
	return 0;
}

 

// input.txt

 

6
BCDEFG
0 1 0 1 0 0
0 0 1 0 0 0
0 0 0 0 0 1
0 1 0 0 0 0
1 0 0 1 0 0
0 0 0 0 1 0
GF