啊啊啊我只会做水题了……

这题就是要求你只删除一条边拆爆所有的奇环，同时不能产生新的gay环，求所有可能的选择方案。

如果说只有一个奇环，那么上面的树边和非树边都是可以拆爆的。但如果有好几个奇环，那么只能选择树边了。奇环的树边部分肯定是若干链，我们只要树上差分标记一下就能求出这些链的交了。

但考虑一件事，如果一个偶环和一个奇环的树边部分相交了，那么删掉其中一边会导致新的奇环出现（证明的话考虑将环异或一下）。所以说在偶环的树边并上的边也不能取。

注意这题图可能不连通……所以要对每个连通块都DFS。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using ll = long long;
const int maxn = 10005;
const int maxm = 20005;
struct Edge {
  int u, v;
  int id;
};
std::vector<Edge> G[maxn];
int n, m;
inline void ins_edge(int u, int v, int id) {
  G[u].push_back((Edge){u, v, id});
  G[v].push_back((Edge){v, u, id});
}

int dep[maxn], anc[maxn][15];
bool vis[maxn];
void dfs_1(int x, int fa = -1) {
  vis[x] = true;
  anc[x][0] = fa;
  for(auto &e : G[x]) {
    int v = e.v;
    if(!vis[v]) {
      dep[v] = dep[x] + 1;
      dfs_1(v, x);
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 14; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) u = a;
  }
  if(u == v) return u;
  for(int j = 14; j >= 0; j --) {
    int a1 = anc[u][j];
    int a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1, v = a2;
    }
  }
  return anc[u][0];
}
bool used[maxm];
int d1[maxn], d2[maxn];
int o_cnt = 0, o_id;
void dfs_2(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    if(used[e.id]) continue;
    used[e.id] = true;
    int v = e.v;
    if(vis[v]) {
      int l = lca(x, v);
      int dis = dep[x] + dep[v] - 2 * dep[l];
      int *d;
      if(dis & 1) {
        d = d2;
      } else {
        d = d1;
        o_cnt ++;
        if(o_cnt == 1) o_id = e.id;
      }
      d[x] ++; d[v] ++; d[l] -= 2;
    } else {
      dfs_2(v);
    }
  }
}
void dfs_3(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    int v = e.v;
    if(!vis[v]) {
      dfs_3(v);
      d1[x] += d1[v];
      d2[x] += d2[v];
    }
  }
}
bool allow[maxm], expc[maxm];
void dfs_4(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    int v = e.v, id = e.id;
    if(!vis[v]) {
      if(d1[v] == o_cnt) {
        allow[id] = true;
      }
      if(d2[v] > 0) {
        expc[id] = true;
      }
      dfs_4(v);
    }
  }
}
std::vector<int> ret;
void solve() {
  memset(anc, -1, sizeof(anc));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_1(i);
  }
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_2(i);
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_3(i);
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_4(i);
  }
  if(o_cnt == 0) {
    for(int i = 1; i <= m; i ++) ret.push_back(i);
  } else {
    for(int i = 1; i <= m; i ++) {
      if(allow[i] && (!expc[i])) {
        ret.push_back(i);
      } else if(o_cnt == 1 && o_id == i) {
        ret.push_back(i);
      }
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v, i);
  }
  solve();
  printf("%d\n", ret.size());
  bool flag = false;
  for(auto i : ret) {
    if(flag) putchar(' ');
    flag = true;
    printf("%d", i);
  }
  puts("");
  return 0;
}

• 相关文章
• 全局相关文章