Problem description

Lao Zhang and Lao Wang love to climb mountains. They must climb Xiangshan once a week. Once, the two people had a dispute about how many paths there were from the east gate to Xianglu peak, so they agreed that who walked the route that the other party didn't walk in a period of time would win.
Given a circuit diagram (undirected connected graph, there may be multiple edges between two vertices), the number of independent paths from the starting point to the end point is calculated by programming, and the relevant path information is output.

Note: independent path means that at least one edge of a path from the starting point to the end point is different from that of other paths, and there is no loop in the path.

Input form

The vertices of the graph are numbered according to the natural number (0,1,2,..., n), where vertex 0 represents the starting point and vertex n-1 represents the ending point. First, input two positive integers n and E from the standard input to represent the number of vertices and edges of the circuit diagram respectively, and then input the information of each edge in the next e line. The specific form is as follows:

<n> <e>
<e1> <vi1> <vj1>
<e2> <vi2> <vj2>
...
<en> <vin> <vjn>

Note: the first row is the number of vertices of the graph, indicating the number of edges of the graph; The second line is the sequence number of the edge (the range of the edge sequence number is between [01000], i.e. including 0 but excluding 1000) and the two vertices of the edge (when there are multiple edges between the two vertices, the sequence number of the edge will be different), separated by a space; others and so on.

Output form

Output all paths from the start point 0 to the end point n-1 (the path is represented by the sequence of edge serial numbers, and there can be no rings in the path). Each line represents a path from the start point to the end point (composed of edge serial numbers, separated by a space in the middle, and the last number followed by enter), and all paths are output in dictionary order.

sample input

6 8
1 0 1
2 1 2
3 2 3
4 2 4
5 3 5
6 4 5
7 0 5
8 0 1

sample output

1 2 3 5
1 2 4 6
7
8 2 3 5
8 2 4 6

Example description

The composition of sample input is as follows:

The first output path 1, 2, 3, 5 represents a path. First go to edge 1 (vertex 0 to vertex 1), then go to edge 2 (vertex 1 to vertex 2), then go to edge 3 (vertex 2 to vertex 3), and then go to edge 5 (vertex 3 to vertex 5) to reach the end point.

code

#include <iostream>
#include<cstring>
#include <algorithm> 
using namespace std;
int N, E, count1 = 0;
string* path;
bool* visit;
int *imPath;				
int site = 0;

typedef struct ArcNode {
	int adjvex;
	int no;
	struct ArcNode* nextarc;			
}ArcNode;

typedef struct VNode {
	ArcNode* first;				
}VNode;

VNode *G;

void InsertNode(VNode& G, int no, int adj) {
	ArcNode* temp;
	if (G.first == NULL) {
		G.first = new ArcNode();
		temp = G.first;
		temp->nextarc = NULL;
	}
	else {
		temp = new ArcNode();
		temp->nextarc = G.first;
		G.first = temp;
	}
	temp->adjvex = adj;
	temp->no = no;

}

void CreatNode(){
	cin >> N >> E;
	G = new VNode[N];
	for (int i = 0; i < N; i++) {
		G[i].first = NULL;
	}

	for (int i = 0; i < E; i++) {
		int no, e1, e2;
		cin >> no >> e1 >> e2;
		InsertNode(G[e1], no, e2);
		InsertNode(G[e2], no, e1);
	}
}

void FindPath(int p) {
	if (p == N - 1) {
		path[count1] = "";
		for (int i = 0; i < site; i++)
			path[count1] += imPath[i] + '0';
		count1++;
		return;
	}
	ArcNode* temp = G[p].first;
	while (temp) {
		if (!visit[temp->adjvex]) {
			visit[temp->adjvex] = true;
			imPath[site++] = temp->no;
			FindPath(temp->adjvex);
			site--;
			visit[temp->adjvex] = false;
		}
		temp = temp->nextarc;
	}
}

void PrintPath() {
	for (int i = 0; i < count1; i++) {
		cout << path[i][0] - '0';
		for (int j = 1; j < path[i].length(); j++)
			cout << ' ' << path[i][j] - '0';
		cout << endl;
	}
}

int main()
{
	CreatNode();
	path = new string[30];
	visit = new bool[N];
	memset(visit, false, N * sizeof(bool));
	visit[0] = true;
	imPath = new int[N];
	FindPath(0);
	sort(path, path + count1);
	PrintPath();
	delete(G);
}