997. Find the Town Judge

题目给定了所有的单向连接的关系，需要我们找出被所有其他节点所连接的唯一节点，且这个节点不指向任何节点

刚开始想要用并查集来做，犯了错误，那就是并查集的连接其实是具有传递性的，更适合用于无向连接，而本题是有向连接且不能进行传递即 A 信任 B，B 信任 C，我们不能认为 A 也信任 C

第一次解法：暴力构建图

key 是被指向的元素，val 是信任了 key 的集合

// time: O(N²)
// space: O(N²)
int findJudge(int N, vector<vector<int>>& trust) {
    if (N==1) return 1;
    unordered_map<int, unordered_set<int> > g;
    for(auto p : trust) {
        if (g.find(p[1])==g.end())
            g.insert({ p[1], unordered_set<int>{ p[0] } });
        else
            g[p[1]].insert(p[0]);
    }

    for(auto&kv : g) {
        if (kv.second.size() == N-1) {
            bool found=true;
            for(auto&kv2 : g) {
                if (kv2.second.find(kv.first)!=kv2.second.end()) {
                    found=false;
                    break;
                }
            }
            if (found) return kv.first;
        }
    }
    return -1;
}

这种方法并不是很理想，毕竟我们关心的只是连接的计数问题，而并非连接的路径

第二种解法：直接进行连接计数

记录每个元素连接别人和被人连接的个数，每个元素需要两个计数器，因此 N 个元素需要两个 vector

// time: O(sizeof(trust))
// space: O(2N)
int findJudge(int N, vector<vector<int>>& trust) {
    vector<int> trusts(N+1, 0);
    vector<int> trusted(N+1, 0);
    for(auto& p : trust) ++trusted[p[1]], ++trusts[p[0]];
    for(int i=1;i<=N;++i)
		if (trusted[i]==N-1 && trusts[i]==0) return i;
    return -1;
}

更好的解法是使用一个 vector 记录 被连接 - 连接其他 的值，当值为 N-1 的时候就符合题目的要求了

// time: O(sizeof(trust))
// space: O(N)
int findJudge(int N, vector<vector<int>>& trust) {
    vector<int> balance(N+1, 0);
    for(auto& p : trust) --balance[p[0]], ++balance[p[1]];
    for(int i=1;i<=N;++i) if (balance[i]==N-1) return i;
    return -1;
}

第三种解法：构建邻接矩阵

int findJudge(int N, vector<vector<int>>& trust) {
  vector<vector<int>> knows(N + 1, vector<int>(N + 1));
  for (auto &t : trust) knows[t[0]][t[1]] = 1;
  return findCelebrity(N, knows);
}

int findCelebrity(int n, vector<vector<int>>& knows, int i = 1) {
  // 通过快速查表找到被所有节点连接的节点（可能是环）
  for (int j = i + 1; j <= n; ++j) if (knows[i][j]) i = j;
  // 验证：关系不是环
  for (int j = 1; j < i; ++j) if (knows[i][j]) return -1;
  // 验证：该节点不连接其他所有节点
  for (int j = 1; j <= n; ++j) if (i != j && !knows[j][i]) return -1;
  return i;
}

可以发现在预处理成邻接矩阵的帮助下，空间复杂度可以降到 O(1)

收获

邻接矩阵的应用
连接计数的方法

#有向图

989. Add to Array-Form of Integer Best Time to Buy and Sell Stock 买卖股票最佳时间系列