Graph Coloring II

如果你能把图三染色，第一行输出0，第二行输出n个整数 $x_1\sim x_n$ 表示每个点的颜色 (0≤ x_i≤ 2)。如果有多种合法方案，你可以输出任意一种。
如果你能找到一个删去其中的边后图仍然联通的简单奇环，第一行输出环长k，第二行输出k个整数 $y_1\sim y_k$ 表示环上结点编号 (1≤ y_i≤ n)，你需要保证y_i和y_i+1之间有边，y₁和y_n之间有边。如果有多种合法方案，你可以输出任意一种。
如果两种情况都是可行的，你可以输出任意一种。
如果两种情况都是不可行的，请输出一行一个整数-1。

C++ 解法, 执行用时: 307ms, 内存消耗: 18992K, 提交时间: 2021-09-26 00:07:12

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+100;
vector<int> G[maxn];
int color[maxn];
int n,m;
queue<int> que;
void bfs()
{
  que.push(1);
  while (!que.empty())
  {
    int u = que.front();
    que.pop();
    if (color[u]!=0)continue;
    color[u]=1;
    for (int v:G[u])color[v]=2;
    for (int v:G[u])for (int vv:G[v])if (!color[vv])
    {
      que.push(vv);
    }
  }
}
bool used[maxn];
vector<int> stak;
void dfs(int u)
{
  used[u]=1;
  stak.push_back(u);
  for (int v:G[u])if (color[v]!=1)
  {
    if (used[v]&&color[v]==color[u])
    {
      vector<int> res;
      while (true)
      {
        res.push_back(stak.back());
        if (res.back()==v)break;
        stak.pop_back();
      }
      printf("%d\n",(int)res.size());
      for (int num:res)printf("%d ",num);
      exit(0);
    }
    if (!used[v])
    {
      if (color[u]==2)color[v]=0;
      else color[v]=2;
      dfs(v);
    }
  }stak.pop_back();
}
int main()
{
  scanf("%d %d",&n,&m);
  for (int i=1,u,v;i<=m;++i)
  {
    scanf("%d %d",&u,&v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  bfs();
  for (int i=1;i<=n;++i)if (!used[i]&&color[i]==2)
  {
    dfs(i);
  }
  printf("0\n");
  for (int i=1;i<=n;++i)printf("%d ",color[i]);
}

详情