滴滴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; }第二题工人和机器求解,只写出暴力,