图|出入度

lcp62

图

/*
交通枢纽: 入度为n-1, 出度为0
*/
class Solution {
public:
int transportationHub(vector<vector<int>>& path) {
int d[1010][2] = {0};
// d[i][0]: i的入度, d[i][1]: i的出度
unordered_set<int> s; // 存哪些城市
for (auto& p : path) {
d[p[0]][1]++, d[p[1]][0]++;
s.insert(p[0]);
s.insert(p[1]);
}

int n = s.size(); // 共n个城市
for (auto city : s) { // 交通枢纽: 入度为n-1, 出度为0的城市
if (d[city][0] == n - 1 && d[city][1] == 0) return city;
}
return -1;
}
};