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