题目描述
修修在黑板上画了一些无向连通图，他发现他可以将这些图的结点用两种颜色染色，满足相邻点不同色。 澜澜不服气，在黑板上画了一个三个点的完全图。修修跟澜澜说，这个图我能找到一个简单奇环。 澜澜又在黑板上画了一个n个点m条边的无向连通图。很可惜这不是一道数数题，修修做不出来了。 澜澜非常得意，作为一位毒瘤出题人，有了好题当然要跟大家分享，于是他把这道题出给你做了。
输入描述:
第一行两个整数n,m (1≤ n,m≤ 3*10 5)，接下来m行每行两个整数a i,b i表示一条边 (1≤ a i,b i≤ n)。 保证图连通，并且不存在重边和自环。
输出描述:
如果你能把图二染色，第一行输出0，第二行输出n个整数 
表示每个点的颜色 (0≤ x i≤ 1)。如果有多种合法方案，你可以输出任意一种。 如果你能找到一个简单奇环，第一行输出环长k，第二行输出k个整数 
表示环上结点编号 (1≤ y i≤ n)，你需要保证y i和y i+1之间有边，y 1和y n之间有边。如果有多种合法方案，你可以输出任意一种。 如果两种情况都是可行的，你只需要输出任意一种。 如果两种情况都是不可行的，请输出一行一个整数-1。
输入
3 2 1 2 1 3
输出
0 0 1 1
输入
3 3 1 2 1 3 2 3
输出
3 1 2 3
题意
给一个无向连通图，有两个选择：用黑色和白色给所有节点涂色，要求相邻节点颜色不能相同；或输出一个有奇数个节点的环。
分析
第一个问题是经典问题，直接选一个点开始涂色，然后用dfs或bfs的顺序为相邻的点依次涂色，涂完所有的点或者遇到矛盾的情况为止；对于第二个问题，奇数个节点的环，如果对这个环进行涂色，那么一定会矛盾，所以可以反过来再结合第一个问题，如果能涂完就直接输出涂色的方案，如果不能完成涂色，那么一定是在中途遇到了奇数个节点的环。因此为了更好的记录涂色的先后关系，这里应该用dfs，并在遇到矛盾情况时，回退到矛盾点被涂色的地方，就得到了一个奇数环。 总的来说，没有奇数环，则涂色一定成功，有奇数环，则输出奇数环，不会有两种都不满足的情况。
总结
原来“简单环”的意思就简单的是环，题意理解偏差了啊，最开始用bfs写了，然后在导出路径的时候发现根本行不通。
代码
#include#include typedef std::vector Vi;#define maxn 300005//链式存边int fst[maxn], to[maxn << 1], nxt[maxn << 1], z = 0;void add(int u, int v) { z++; to[z] = v; nxt[z] = fst[u]; fst[u] = z; z++; to[z] = u; nxt[z] = fst[v]; fst[v] = z;}int n, m;int clr[maxn];Vi rt;int isodd/*是奇数环的标记*/, rat/*涂色矛盾发生的地方，也就是奇数环的起点/终点*/, ended/*完成了环的记录*/;//直接涂色void dfs(int cid) { int nid; for (int ln = fst[cid]; ln; ln = nxt[ln]) { nid = to[ln]; if (clr[nid] == -1) { clr[nid] = !clr[cid]; dfs(nid); if (ended)return; if (isodd) { rt.push_back(nid); if (cid == rat)//已经回退到环的起点 ended = 1; return; } } else if (clr[nid] == clr[cid]) { //遇到矛盾，开始回退 rat = nid; rt.push_back(nid); isodd = 1; ended = 0; return; } }}int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i)clr[i] = -1; int ai, bi; for (int i = 0; i