HDOJ 5424-Rikka with Graph II

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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *