链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
修修在黑板上画了一些无向连通图，他发现他可以将这些图的结点用两种颜色染色，满足相邻点不同色。
澜澜不服气，在黑板上画了一个三个点的完全图。修修跟澜澜说，这个图我能找到一个简单奇环。
澜澜又在黑板上画了一个n个点m条边的无向连通图。很可惜这不是一道数数题，修修做不出来了。
澜澜非常得意，作为一位毒瘤出题人，有了好题当然要跟大家分享，于是他把这道题出给你做了。
第一行两个整数n,m (1≤ n,m≤ 3*105)，接下来m行每行两个整数ai,bi表示一条边 (1≤ ai,bi≤ n)。 保证图连通，并且不存在重边和自环。输出描述:
如果你能把图二染色，第一行输出0，第二行输出n个整数x1∼xnx_1sim x_nx1∼xn表示每个点的颜色 (0≤ xi≤ 1)。如果有多种合法方案，你可以输出任意一种。 如果你能找到一个简单奇环，第一行输出环长k，第二行输出k个整数y1∼yky_1sim y_ky1∼yk表示环上结点编号 (1≤ yi≤ n)，你需要保证yi和yi+1之间有边，y1和yn之间有边。如果有多种合法方案，你可以输出任意一种。 如果两种情况都是可行的，你只需要输出任意一种。 如果两种情况都是不可行的，请输出一行一个整数-1。
示例1
输入3 2 1 2 1 3输出
0 0 1 1
示例2
输入3 3 1 2 1 3 2 3输出
3 1 2 3
通过分析可以得到一个结论，有单奇环一定不能染色成功，能染色成功一定没单奇环
因此只需要枚举染色或者枚举单奇环即可
下面是枚举单奇环的代码
#includeusing namespace std; using ll = long long; int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 }; //using lll = __int128;template istream& read(T& x, istream& cin = std::cin);template ostream& write(T x, ostream& cout = std::cout);ostream& operator<<(ostream& cout, lll x);istream& operator>>(istream& cin, lll &x); bool check(int i, int j); const int N = 3e5 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f; int n, m, depth[N], pre[N]; vector g[N], ji; bool st[N]; void init() { cin >> n >> m; for (int i = 0; i < m; i ++) { int x, y; cin >> x >> y; g[x].emplace_back(y); g[y].emplace_back(x); } // cout << "初始化完成n"; return; } int s, r; //记录环的起点和终点 bool flag = 0; //是否找到单奇环 void dfs(int u, int p) { st[u] = 1; pre[u] = p; //记录当前点的前继节点 depth[u] = depth[p] + 1; //记录当前点的深度 for (auto rit : g[u]) { if (flag) return; //如果有分支找到单奇环提前终止 if (st[rit]) { //如果下一个节点已经被访问过那么出现了环 if (rit == p) continue; //如果下一个节点是当前节点的父节点则跳过 if ((depth[u] - depth[rit]) % 2 == 0) { //如果是单奇环则环起点和重点的深度之差为偶数 s = u, r = rit; //记录环的起点和终点 flag = 1; return; } continue; } dfs(rit, u); } } void solve() { dfs(1, 0); if (!flag) { //如果没发现单奇环则一定染色成功 cout << "0n"; for (int i = 1; i <= n; i ++) { cout << (depth[i] & 1) << " "; //depth的奇偶可以分辨颜色 } } else { while (s ^ r) { //通过前继节点找到环的所有节点 ji.emplace_back(s); s = pre[s]; } ji.emplace_back(s); cout << ji.size() << endl; for (auto &rit : ji) cout << rit << " "; } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(6) << fixed;//保留6位小数从小数点后计数 int TT = 1; //cin >> TT; for (int ii = 0; ii < TT; init(), solve(), ii++, cout << "n") {} return 0; } //template istream& read(T& x, istream& cin) {T num = 0; bool f = 0; char ch = 0;while (!isdigit(ch)) { f |= ch == '-'; if (!cin.get(ch)) return cin; }while (isdigit(ch)) { num = (num << 3) + (num << 1) + (ch ^ 48); if (!cin.get(ch)) return cin; }x = f ? -num : num; return cin;}template ostream& write(T x, ostream& cout) {if (x < 0) cout.put('-'), x = -x;if (x > 9) write(x / 10);cout.put(x % 10 + '0'); return cout;}ostream& operator<<(ostream& cout, lll x) {write(x);return cout;}istream& operator>>(istream& cin, lll &x) {return read(x);}
