1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| void dfs1(vector<vector<int>>& adj, vector<int>& vis, vector<int>& st, int u) { vis[u] = true; for(auto& v : adj[u]) { if(!vis[v]) dfs1(adj, vis, st, v); } st.push_back(u); }
void dfs2(vector<vector<int>>& radj, vector<int>& vis, vector<int>& rep, int u, int r) { vis[u] = true; rep[u] = r; for(auto& v : radj[u]) { if(!vis[v]) dfs2(radj, vis, rep, v, r); } }
int airportConnections(vector<string> airports, vector<vector<string>> routes, string startingAirport) { unordered_map<string, int> idmp; int id = 1, n = airports.size();
for(auto& airport : airports) idmp[airport] = id++;
vector<vector<int>> adj(n + 1), radj(n + 1); vector<int> rep(n + 1), vis1(n + 1), vis2(n + 1), rpath(n + 1); vector<int> st; unordered_set<int> endPoints; for(auto& route : routes) { int u = idmp[route[0]], v = idmp[route[1]]; adj[u].push_back(v); radj[v].push_back(u); } for(int i = 1; i <= n; i++) if(!vis1[i]) dfs1(adj,vis1,st,i); while(!st.empty()) { auto u = st.back(); st.pop_back(); if(!vis2[u]) { dfs2(radj, vis2, rep, u, u); endPoints.insert(u); } } for(int i = 1; i <= n; i++) { for(auto& v : radj[i]) if(rep[v] != rep[i]) endPoints.erase(rep[i]); } endPoints.erase(rep[idmp[startingAirport]]);
return endPoints.size(); }
|