tj

上课照抄老师代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = 10010;

struct Edge {
    int to, next, id;
} e[M * 2];

int head[N], tot = 1;
int n, m;
int color[N], depth[N];
int odd_cnt[N], even_cnt[N];
int odd_cycle;
bool vis[N];
int tree_edge_parent[N];  // 记录每条树边对应的子节点
bool is_tree[M];
int edge_u[M], edge_v[M];
vector<int> ans;

void add_edge(int u, int v, int id) {
    e[++tot] = {v, head[u], id};
    head[u] = tot;
}

void dfs(int u, int p, int d, int pe) {
    vis[u] = true;
    color[u] = p;
    depth[u] = d;
    
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        int id = e[i].id;
        
        if (depth[v] == 0) {
            // 树边
            is_tree[id] = true;
            tree_edge_parent[id] = v;
            dfs(v, p ^ 1, d + 1, id);
            odd_cnt[u] += odd_cnt[v];
            even_cnt[u] += even_cnt[v];
        } else if (depth[v] < depth[u] && id != pe) {
            // 非树边，且是返祖边
            if (color[u] == color[v]) {
                // 奇环
                odd_cycle++;
                odd_cnt[u]++;
                odd_cnt[v]--;
            } else {
                // 偶环
                even_cnt[u]++;
                even_cnt[v]--;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edge_u[i] = u, edge_v[i] = v;
        add_edge(u, v, i);
        add_edge(v, u, i);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i, 0, 1, 0);
        }
    }
    
    if (odd_cycle == 0) {
        cout << m << "\n";
        for (int i = 1; i <= m; i++) {
            cout << i << " ";
        }
        cout << "\n";
        return 0;
    }
    
    // 检查树边
    for (int i = 1; i <= m; i++) {
        if (is_tree[i]) {
            int u = edge_u[i], v = edge_v[i];
            // 找到子节点
            int child = (depth[u] > depth[v]) ? u : v;
            if (odd_cnt[child] == odd_cycle && even_cnt[child] == 0) {
                ans.push_back(i);
            }
        } else if (odd_cycle == 1) {
            // 只有一个奇环时，非树边如果在奇环上也是好边
            int u = edge_u[i], v = edge_v[i];
            if (depth[u] < depth[v]) swap(u, v);
            // 检查这条边是否在唯一的奇环上
            if (color[u] == color[v]) {
                ans.push_back(i);
            }
        }
    }
    
    cout << ans.size() << "\n";
    for (int i : ans) {
        cout << i << " ";
    }
    cout << "\n";
    
    return 0;
}