dfs

题意：

分析：

深搜没学好啊！
我们会发现，这其实就是一个判断图是否是二分图的过程！
那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！

染色部分容易，广搜深搜都可以，分深度奇偶染色即可。
但是，要我们找环，就有点困难了。
因为要是环，所以我们选择深搜，因为要打印出来，所以我们要记录他的父节点！

代码如下：

#include<iostream>
using namespace std;
const int max_n = 3e5 + 100;
const int max_m = 3e5 + 100;
int n, m;
struct edge
{
    int to, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;

void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

bool map[max_n];
bool vis[max_n];
int pre[max_n];
bool dfs(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!vis[v]) vis[v] = 1, map[v] = !map[u], pre[v] = u, dfs(v);
        else if (map[v] == map[u]) {
            int i;int s = 1;
            for (i = u;i != v;i = pre[i])s++;
            cout << s << endl;
            for (i = u;i != v;i = pre[i])cout << i << " ";
            cout << v << endl;
            exit(0);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        add(u, v);add(v, u);
    }dfs(1);
    cout << 0 << endl;
    for (int i = 1;i <= n;i++)cout << map[i] << " ";
}