C++ 算法：判断是否存在可行观光路线

题目描述

给定$m$个点，$s$条边，每条边有一个方向（或双向），要求从一个点出发，经过所有的点恰好一次，最后回到起点。问是否存在这样的路径。

输入格式

第一行，一个正整数$n$，表示测试数据组数。

接下来，每一组数据的第一行包含两个正整数$m$和$s$，表示点数和边数。

接下来$s$行，每行三个整数$x_i,y_i,d_i$，表示第$i$条边连接$x_i$和$y_i$两个点，如果$d_i=1$，表示该边是单向的，否则为双向。

可以保证存在一个点，从该点可以到达所有的点。

输出格式

每组数据输出一行，如果能够通过给定的边走遍每个点且回到起点，则输出possible，否则输出impossible。

样例输入

4 5 8 2 1 0 1 3 0 4 1 1 1 5 0 5 4 1 3 4 0 4 2 1 2 2 0 4 4 1 2 1 2 3 0 3 4 0 1 4 1 3 3 1 2 0 2 3 0 3 2 0 3 4 1 2 0 2 3 1 1 2 0 3 2 0

样例输出

possible impossible impossible possible

算法

一道图论题。

由于题目中要求遍历所有的点恰好一次，因此我们可以考虑用欧拉回路来解决问题。

欧拉回路的定义：对于无向图，如果存在一条路径，使得它经过每条边恰好一次，称这条路径为欧拉回路。对于有向图，如果存在一条路径，使得它经过每条边恰好一次，称这条路径为欧拉回路。

那么我们可以先判断这张图是否存在欧拉回路，如果存在，则说明可以从某个点开始，遍历所有的点恰好一次，最后回到起点。否则，无解。

关于如何判断图是否存在欧拉回路，这里简单介绍两种方法：

Fleury算法

Fleury算法可以用于求无向图中的欧拉回路。

步骤：

从任意一个节点出发，如果存在一条边，删去这条边，并往这个节点走；重复上述操作，直到无法继续，如果已经遍历完所有的边，则存在欧拉回路；否则，就需要回溯到一个之前的节点，继续遍历。

注意：这里需要注意的是，如果有一个点的度数为奇数，则无法存在欧拉回路。

Hierholzer算法

Hierholzer算法可以用于求有向图中的欧拉回路。

步骤：

任选一个点开始，沿着任意一条边走，直到无法继续为止；

如果这条路径经过了某个节点，且从该节点还有出边未被访问过，就从该节点继续走，直到无法继续为止，并将走过的边存起来；

如果这条路径经过了某个节点，且该节点的所有出边都被访问过了，就将该节点加入到路径中，并将路径中从该节点开始的部分（不包括该节点）反转，然后继续从该节点走，直到无法继续为止，并将走过的边存起来；

重复上述操作，直到所有的边都被遍历过，此时得到的路径就是欧拉回路。

注意：这里需要注意的是，如果存在一个点的入度和出度不相等，则无法存在欧拉回路。

C++ 代码

下面给出使用Fleury算法的代码：