滴滴9/19笔试第一题答案
第一题垃圾车，染色问题，因为每个节点最多两条边，因此只能是环或者链，是链的话无影响，是环的话，当环长度为偶数时无影响，长度为奇数时有一袋垃圾必然抛弃，因此遍历图计算所有环的长度即可
int dfs(int start, int pre, int cur, int len, vector<vector<int>> &graph, unordered_set<int> &visited) {
// 返回环的长度，若不存在环，返回0
if (pre != -1 && start == cur) return len-1;
if (visited.count(cur)) return 0;
visited.insert(cur);
for (int next : graph[cur]) {
if (next == pre) continue;
return dfs(start, cur, next, len + 1, graph, visited);
}
return 0;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>());
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
graph[a - 1].push_back(b - 1);
graph[b - 1].push_back(a - 1);
}
int free = n;
unordered_set<int> visited;
for (int i = 0; i < n; ++i) {
if (dfs(i, -1, i, 1, graph, visited) & 1) free--;
}
cout << free / 2 * 2 << endl;
return 0;
} 第二题工人和机器求解，只写出暴力，
查看12道真题和解析
，白菜就是我的天花板