int cmp(const void* a, const void* b){ return (*(int**)a)[0] > (*(int**)b)[0]; } int* gardenNoAdj(int N, int** paths, int pathsSize, int* pathsColSize, int* returnSize){ int i,j,k,temp,pst,cnt=2; for (i = 0; i < pathsSize; i++) { if (paths[i][0] < paths[i][1]) { temp = paths[i][0]; paths[i][0] = paths[i][1]; paths[i][1] = temp; } } qsort(paths, pathsSize, sizeof(int*), cmp); int* arr = (int*)malloc(N * sizeof(int)); for (i = 0; i < N; i++) arr[i] = 1; for (i = 0; i < pathsSize;) { if (paths[i][0] != cnt) { arr[cnt - 1] = 1; } else { int t[] = { 0, 1, 2, 3, 4 }; pst = 0; while (i < pathsSize && paths[i][0] == cnt && pst<3){ if (t[arr[paths[i][1] - 1]]){ t[arr[paths[i][1] - 1]] = 0; pst++; } i++; } for (j = 1; j < 5; j ++) { if (t[j]) { arr[cnt - 1] = t[j]; break; } } } cnt++; } *returnSize = N; return arr; }
struct node { int paths[4]; int path_num; int color; }; int* gardenNoAdj(int N, int** paths, int pathsSize, int* pathsColSize, int* returnSize){ if (N == 0) { *returnSize = 0; return NULL; } int *res = (int *)malloc(sizeof(int) * N); memset(res, 0, sizeof(int) * N); struct node *Nodes = (struct node *)malloc(sizeof(struct node) * N); memset(Nodes, 0, sizeof(struct node) * N); /* 构造邻接矩阵 */ for(int i = 0; i < pathsSize; i++) { int start = paths[i][0] - 1; int end = paths[i][1] - 1; Nodes[start].paths[Nodes[start].path_num] = end; Nodes[start].path_num++; Nodes[end].paths[Nodes[end].path_num] = start; Nodes[end].path_num++; } /* 填充颜色 */ for(int i = 0; i < N; i++) { int set[4] = {-1, -1, -1, -1}; for(int path_i = 0; path_i < Nodes[i].path_num; path_i++) { int n_path = Nodes[i].paths[path_i]; if (res[n_path] != 0) { //这个颜色不能有 set[res[n_path] - 1] = 0; } } for(int j = 0; j < 4; j++) { if (set[j] == -1) { res[i] = j + 1; break; } } } *returnSize = N; return res; }