第一行一个数表示数据组数
每组数据第一行一个数表示树有个节点
接下来行每行个数,表示和点有一条边相连
每组数据对应一行,如果牛牛赢则输出”niuniu",如果牛妹赢输出"niumei“。
2 7 3 6 1 2 3 1 7 4 5 7 1 4 4 1 4 4 2 2 3
niuniu niumei
第一个用例树的形态如下:第二个用例树的形态如下:
#include<iostream> #include<vector> #include<queue> #include<unordered_map> #include<unordered_set> using namespace std; struct node { int cur_node; int pre_node; int deep; node(int a, int b, int c) :cur_node(a), pre_node(b), deep(c) {} node():cur_node(0),pre_node(0),deep(0){} }; pair<int, int> find_way(vector<vector<int>>& map, int n) // 寻找边界节点 { queue<node> queue; node tmp(0, -1, 0); queue.push(tmp); unordered_map<int, node> visited; visited[0] = tmp; while (!queue.empty()) { tmp = queue.front(); queue.pop(); if (tmp.cur_node == n - 1) // 到达节点n终止bfs break; for (int i = 0; i < map[tmp.cur_node].size(); i++) { int t = map[tmp.cur_node][i]; if (t == 0) continue; if (visited.find(i) != visited.end()) continue; node next(i, tmp.cur_node, tmp.deep + 1); visited[i] = next; queue.push(next); } } node fin_node = visited[n - 1]; // 倒推回去找途径的节点 int op_num = (fin_node.deep - 1) / 2; //计算牛妹拥有的节点数 int cnt = 0; node cur = fin_node; while (cnt != op_num) { int pre_num = cur.pre_node; cnt++; cur = visited[pre_num]; } return pair<int, int>(cur.cur_node, cur.pre_node); // 返回牛牛和牛妹的边界节点 } int bfs(vector<vector<int>>& map, int start, int bound, int n) //计算两人各拥有的空白节点数 { unordered_set<int> visited; queue<int> queue; int cnt = 0; queue.push(start); visited.insert(start); while (!queue.empty()) { int cur_node = queue.front(); queue.pop(); for (int i = 0; i < map[cur_node].size(); i++) { int t = map[cur_node][i]; if (t == 0 || i == bound) continue; if (visited.find(i) != visited.end()) continue; cnt++; visited.insert(i); queue.push(i); } } return cnt; } int main() { int T; cin >> T; for (int tt = 0; tt < T; tt++) { int n; cin >> n; vector<vector<int>> map(n); int x, y; for (int i = 0; i < n - 1; i++) // 建无向图 { cin >> x >> y; map[x - 1].emplace_back(y - 1); map[y - 1].emplace_back(x - 1); } auto bound_node = find_way(map, n); int niuniu = bfs(map, 0, bound_node.first, n); int niumei = bfs(map, n - 1, bound_node.second, n); if (niuniu > niumei) cout << "niuniu" << endl; else cout << "niumei" << endl; } }
#include <iostream> #include <queue> #include <unordered_map> #include <vector> using namespace std; int main() { int n = 0; cin >> n; while (cin >> n) { unordered_map<int, vector<int>> ump; for (int i = 0; i < n-1; i++) { int x, y; cin >> x >> y; ump[x].push_back(y); ump[y].push_back(x); } vector<pair<int, vector<int>>> tree(n+1, make_pair(-1, vector<int>())); tree[1].first = 0; queue<int> q; q.push(1); while (!q.empty()) { int cur = q.front(); q.pop(); for (int i : ump[cur]) { if (tree[i].first == -1) { tree[i].first = cur; tree[cur].second.push_back(i); q.push(i); } } } vector<int> path; int root = n; while (root != 0) { path.push_back(root); root = tree[root].first; } int whiteroot = path[-1 + path.size() / 2]; q = queue<int>(); q.push(whiteroot); int whitesize = 0; while (!q.empty()) { int cur = q.front(); q.pop(); whitesize++; for (int child : tree[cur].second) { q.push(child); } } int blacksize = n - whitesize; if (blacksize > whitesize) { cout << "niuniu" << endl; } else { cout << "niumei" << endl; } } return 0; }
#include <iostream> #include <array> #include <vector> using namespace std; const int MAXN = 1e5; array<vector<int>, MAXN> edges; array<int, MAXN> next_index; vector<int> path; int dfs(int start, int dest){ path.clear(); next_index.fill(-1); path.emplace_back(start); next_index[start] = 0; int count = 1; while(!path.empty() && path.back() != dest){ int p = path.back(); while(next_index[p] < edges[p].size() && next_index[edges[p][next_index[p]]] > 0) next_index[p]++; if(next_index[p] >= edges[p].size()) path.pop_back(); else{ int expand = edges[p][next_index[p]]; path.emplace_back(expand); next_index[expand] = 0; count++; next_index[p]++; } } return count; } int main(){ int T; cin >> T; for(int t = 0; t < T; t++){ int n, a, b; cin >> n; for(int i = 0; i < n; i++) edges[i].clear(); for(int i = 0; i < n - 1; i++){ cin >> a >> b; edges[a - 1].emplace_back(b - 1); edges[b - 1].emplace_back(a - 1); } // 从0深搜找n-1顶点, 找到时停止 dfs(0, n - 1); // 找到path中间黑和白的关键节点, 让黑关键节点断掉与白节点联系, 进行深搜统计节点数 int black_key = path[(path.size() - 1) / 2]; int white_key = path[(path.size() + 1) / 2]; for(auto it = edges[black_key].begin(); it != edges[black_key].end(); it++){ if(*it == white_key){ edges[black_key].erase(it); break; } } int black_count = dfs(black_key, -1); int white_count = n - black_count; if(black_count > white_count) cout << "niuniu\n"; else cout << "niumei\n"; } }