哈密顿图 poj 1776

xiaoxiao2021-02-27  320

哈密顿图解析:http://blog.csdn.net/pi9nc/article/details/9219971

#include <cstdio> #include <cstring> using namespace std; #define maxn 1010 bool graph[maxn][maxn]; int next[maxn]; int head, n; char str[maxn << 1]; int main() { int i, j, k; while(~scanf("%d\n", &n)){ for(i = 0; i < n; i ++) { gets(str); for(j = 0; j < n; j ++) graph[i][j] = str[j << 1] - '0'; } memset(next, 0xff, sizeof(next)); head = 0; for(i = 1; i < n; i++) {//遍历未进入的点 if(graph[i][head]) {//头插 next[i] = head; head = i; continue; } j = head; k = next[j]; while(k != -1) {//遍历进入的点 if(graph[j][i] && graph[i][k]) break; j = k; k = next[j]; } next[i] = k; next[j] = i; } printf("1\n%d\n", n); for(i = 0; i < n; i++) { printf(i == 0 ? "%d" : " %d", head + 1); head = next[head]; } printf("\n"); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-5237.html

最新回复(0)