HDOJ 5424-Rikka with Graph II Rikka with Graph II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 379 Accepted Submission(s): 94 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path. It is too difficult for Rikka. Can you help her? Input There are no more than 100 testcases. For each testcase, the first line contains a number n(1≤n≤1000). Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. Output For each testcase, if there exist a Hamiltonian path print “YES” , otherwise print “NO”. Sample Input 4 1 1 1 2 2 3 2 4 3 1 2 2 3 3 1 Sample Output NO YES Hint For the second testcase, One of the path is 1->2->3 If you doesn’t know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path). Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422
这题题意很明确，判断一个无向图中是否存在哈密顿路径，注意不是哈密顿回路。
由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次，形成的路径称为哈密顿路径，闭合的哈密顿路径称作哈密顿回路，含有哈密顿回路的图称为哈密顿图。本来判断一个常规图中是否存在哈密顿路径是NP完全问题，不可能有多项式解，所以如果依次对每个点DFS，肯定超时。 但是这题很特殊，图中只有n个点，n条边！如果存在哈密顿路径L，则路径长度为n-1条边，设L两个端点为A,B，此时还剩下一条边a，这条边有三种情况： 1）a在L的内部连接，这时A,B的度数都为1，其他点的度数为2或3； 2）a一端在A（或B），另一端在L的内部，这时L的另一个端点B（或A）的度数为1，其他点的度数为2或3； 3）a连接了A,B，此时所有点的度数都为2。 如果存在哈密顿路径，这三种情况下，L的某个端点的度数都是最少的。所以可以先找到度数最小的点，再从这个点开始DFS，这样只需要一次DFS就可以判断是否存在哈密顿路径。 当然要先判断这个图是否连通，我起初使用了并查集，但是超时，郁闷。后来发现，如果哈密顿路径存在，则肯定连通，且此时读数为1点不超过2个，所以可以用这个条件判断是否连通。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; const int kMaxN = 1005; int degree[kMaxN]; vector<vector<int>> path; int visit[kMaxN]; int n, done; bool DFS(int s) { done++; visit[s] = 1; if (done == n) return true; int v; for (int i = 0; i < path[s].size(); i++) { v = path[s][i]; if (!visit[v]) { if (DFS(v)) return true; } } done–; visit[s] = 0; return false; } bool CheckHamiltonian() { int min_degree = n + 1, bad_node_num = 0, id; for (int i = 1; i <= n; i++) { if (degree[i] && degree[i] < min_degree) { min_degree = degree[i]; id = i; } if (degree[i] <= 1) bad_node_num++; } if (bad_node_num > 2) return false; memset(visit, 0, sizeof(visit)); done = 0; return DFS(id); } int main() { //freopen("input.txt", "r", stdin); while (~scanf("%d", &n)) { memset(degree, 0, sizeof(degree)); path.clear(); path.resize(n + 1); int u, v; for (int i = 0; i < n; i++) { scanf("%d %d", &u, &v); if (u == v) continue; degree[u]++; degree[v]++; path[u].push_back(v); path[v].push_back(u); } if (CheckHamiltonian()) printf("YES\n"); else printf("NO\n"); } return 0; } [/cpp] 本代码提交AC，用时93MS，内存1800K。]]>