| 18 | ans.push_back(u); |
| 19 | } |
| 20 | int solve(int n) { |
| 21 | int edges = 0; |
| 22 | vector<int> in(n + 1, 0), out(n + 1, 0); |
| 23 | for (int u = 1; u <= n; u++) { |
| 24 | for (auto v : g[u]) in[v]++, out[u]++, edges++; |
| 25 | } |
| 26 | int ok = 1, cnt1 = 0, cnt2 = 0, root = 0; |
| 27 | for (int i = 1; i <= n; i++) { |
| 28 | if (in[i] - out[i] == 1) cnt1++; |
| 29 | if (out[i] - in[i] == 1) cnt2++, root = i; |
| 30 | if (abs(in[i] - out[i]) > 1) ok = 0; |
| 31 | } |
| 32 | if (cnt1 > 1 || cnt2 > 1) ok = 0; |
| 33 | if (!ok) return 0; |
| 34 | if (root == 0) { |
| 35 | for (int i = 1; i <= n; i++) if (out[i]) root = i; |
| 36 | } |
| 37 | if (root == 0) return 1; //empty graph |
| 38 | dfs(root); |
| 39 | if (ans.size() != edges + 1) return 0; //connectivity |
| 40 | reverse(ans.begin(), ans.end()); |
| 41 | return 1; |
| 42 | } |
| 43 | map<string, int> mp; |
| 44 | string id[N]; |
| 45 | int T = 0; |