Round C APAC Test 2017 Problem C. Evaluation（拓扑排序）

题目链接

https://code.google.com/codejam/contest/6274486/dashboard#s=p2

题意

给定若干个等式，这些等式的顺序可以交换。 等式左边的值依赖于右边的值，要求判断等式是否合法。

思路

我们要解决的问题就是判断这些变量是否存在相互依赖的关系。 假如a = f(b, c)。那么a依赖于b和c，我们就从b和c分别连一条边到a。最后要判断的问题就是这个图是否存在环。

细节

注意假如a = f(b, c)，即a依赖于b和c，那么b和c必须要在等式左边出现过（即b，c一定能够被算出来）

代码

#include <bits/stdc++.h> using namespace std; inline int in() {int x; scanf("%d", &x); return x;} #define pr(x) {cout << #x << ' ' << x << endl;} const int maxn = 100000 + 5; const int maxm = 2005; vector<int> G[maxn]; int In[maxn], n, tot, musthas[maxn]; vector<int> has; char s[maxm]; map<string, int> mmp; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); memset(In, 0, sizeof(In)); memset(musthas, 0, sizeof(musthas)); mmp.clear(); has.clear(); n = 0; tot = 0; } void pre(string s) { bool flag = false; int k = s.find("="); //create to string sv = s.substr(0, k); if (mmp.find(sv) == mmp.end()) mmp[sv] = ++n; int v = mmp[sv]; has.push_back(v); //create from string ss = ""; vector<int> tmp; for (int i = k + 1; i < s.length(); i++) { if (s[i] == '(') {flag = true; continue;} if (s[i] == ')') break; if (flag) { if (s[i] == ',' || i == s.length() - 2) { if (i == s.length() - 2 && s[i] != ',') ss += s[i]; if (mmp.find(ss) == mmp.end()) mmp[ss] = ++n; int u = mmp[ss]; musthas[u] = 1; G[u].push_back(v); In[v]++; ss = ""; } else { ss += s[i]; } } } } bool nocircle() { queue<int> q; int cnt = 0; for (int i = 1; i <= n; i++) if (!In[i]) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (auto v : G[u]) { In[v]--; if (!In[v]) q.push(v); } } return cnt == n; } int main() { int T = in(); int kase = 0; while (T--) { init(); int ca = in(); while (ca--) { string s; cin >> s; pre(s); } cout << "Case #" << ++kase << ": "; bool fl = false; for (auto x : has) { if (musthas[x]) musthas[x] = 0; } for (int i = 1; i <= n; i++) { if (musthas[i]) { cout << "BAD" << endl; fl = true; break; } } if (!fl) { if (nocircle()) cout << "GOOD" << endl; else cout << "BAD" << endl; } } return 0; }