相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4878
解题报告
我们搞出$DFS$生成树
如果树高大于$k$,那么显然可以找出长度为$k$的简单路径
如果树高$\le k$的话,因为非树边一定是返祖边,所以把深度作为颜色就可以$k$染色了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1009; const int M = 20009; int n,m,k,E,head[N],nxt[M],to[M]; int DONE,fa[N],dep[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void AddEdge(int u, int v) { to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } void DFS(int w, int f) { dep[w] = dep[f] + 1; fa[w] = f; if (dep[w] > k) { DONE = 1; printf("path "); for (; 1; w = fa[w]) { printf("%d ", w); if (w == fa[w]) { break; } } cout<<endl; } else { for (int i = head[w]; i && !DONE; i = nxt[i]) { if (!dep[to[i]]) { DFS(to[i], w); } } } } int main() { #ifdef DBG freopen("11input.in", "r", stdin); #endif for (int T = read(); T; T--) { memset(head, 0, sizeof(head)); n = read(); m = read(); k = read(); E = DONE = 0; for (int i = 1; i <= m; i++) { AddEdge(read(), read()); } memset(dep, 0, sizeof(dep)); for (int i = 1; i <= n && !DONE; ++i) { if (!dep[i]) { DFS(i, i); } } if (!DONE) { printf("color "); for (int i = 1; i <= n; ++i) { printf("%d ", dep[i]); } cout<<endl; } } return 0; }