204 汉密尔顿回路

// 204 汉密尔顿回路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/14/problem/632


给你一张无向简单图，请问能否从指定起点出发找到一条汉密尔顿回路。

输入格式
第一行两个整数 n,m，表示图的顶点数和边数，顶点编号从 1到 n。

接下来 m行，每行两个整数 x,y，表示 x号点和 y号点之间有一条边。

接下来一行，一个整数 k，表示起始节点编号。

输出格式 
输出一行一个字符串，如果能找到从 k号点出发的汉密尔顿回路，输出 Yes， 否则输出 No。

样例输入
4 5
1 2
2 3
1 3
1 4
2 4
4
样例输出
Yes
数据规模
对于所有数据，保证 2≤n≤8,0≤m≤n(n−1)/2,1≤x,y,k≤n。
*/


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>


using namespace std;

const int N = 10, M = 60;
int h[N], e[M], ne[M], idx;
int n, m, k;
int vis[N], cnt;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


bool dfs(int x) {
	vis[x] = 1; cnt++;
	if (cnt == n && x == k) {
		return true;
	}
	else if (cnt == n) {
		vis[x] = 0; cnt--;
		return false;
	}

	for (int i = h[x]; i != -1; i=ne[i]) {
		int j = e[i];
		if (vis[j]==0 && dfs(j)) return true;
	}
	vis[x] = 0; cnt--;

	return false;
}


int main() {
	cin >> n >> m ;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		add(a, b); add(b, a);
	}
	cin >> k;
	int flag = 0;
	for (int i = 1; i <= n; i++) {
		if (i == k) continue;
		if (dfs(i)) {
			flag = 1;
			break;
		}
	}

	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}