WA#22,求问题,求调
  • 板块CF19E Fairy
  • 楼主__yabnto__
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/30 18:40
  • 上次更新2023/11/3 00:18:33
查看原帖
WA#22,求问题,求调
755408
__yabnto__楼主2023/8/30 18:40
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

const int MaxN = 1e4 + 10;

int n, m;
vector<int> g[MaxN];
set<int> ans;
bool vis[MaxN], col[MaxN];
map<int, int> id[MaxN];

void DFS(int x, int fa, bool c) {
  if (vis[x]) {
    if (col[x] != c) {
      ans.insert(id[x][fa]);
    }
    return;
  }
  vis[x] = 1;
  col[x] = c;
  for (int i : g[x]) {
    DFS(i, x, !c);
  }
  return;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    id[u][v] = id[v][u] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      DFS(i, 0, 0);
    }
  }
  if (ans.empty()) {
    cout << m << endl;
    for (int i = 1; i <= m; i++) {
      cout << i << " ";
    }
    return 0;
  }
  cout << ans.size() << endl;
  for (int i : ans) {
    cout << i << " ";
  }
  return 0;
}
2023/8/30 18:40
加载中...