世界人民大团结 - 题解 - TeMenHu

1
zhangjin1 LV 10 @ 2026-8-17 21:26:58

$$#include using namespace std; int n, a, b, deg[7], ptr[7]; vector<tuple> adj[7]; bool used[100]; bool connected() { int s = -1; for (int v = 0; v < 7; v++) if (deg[v]) s = v; if (s == -1) return true; set vis; stack st; st.push(s); vis.insert(s); while (!st.empty()) { int v = st.top(); st.pop(); for (auto& [u,i,d] : adj[v]) if (!vis.count(u)) vis.insert(u), st.push(u); } for (int v = 0; v < 7; v++) if (deg[v] && !vis.count(v)) return false; return true; } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a >> b; adj[a].push_back({b,i,'+'}); adj[b].push_back({a,i,'-'}); deg[a]++; deg[b]++; } int odd = 0, start = 0; for (int v = 0; v < 7; v++) if (deg[v] % 2) odd++, start = v; if ((odd != 0 && odd != 2) || !connected()) { cout << "NoSolution"; return 0; } vector<pair> path; stack<tuple> st; st.push({start,-1,' '}); while (!st.empty()) { int v = get<0>(st.top()); bool f = false; while (ptr[v] < (int)adj[v].size()) { auto& [u,i,d] = adj[v][ptr[v]]; if (used[i]) { ptr[v]++; continue; } used[i] = true; ptr[v]++; st.push({u,i,d}); f = true; break; } if (!f) { auto [x,i,d] = st.top(); st.pop(); if (i != -1) path.push_back({i,d}); } } reverse(path.begin(), path.end()); if ((int)path.size() != n) cout << "NoSolution"; else for (auto& [i,d] : path) cout << i+1 << " " << d << "\n"; } $$
//gaygaygaygaygaygaygay

ID

1980

时间

1000ms

内存

256MiB

难度

10

标签

竞赛
NOIP

递交数

已通过

1

上传者