LeetCode 135. 重新规划路线
原题链接
中等
作者:
あ
,
2022-01-18 16:41:22
,
所有人可见
,
阅读 223
图+BFS
思路
见: https://leetcode-cn.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/solution/clin-jie-biao-bfsshi-xian-by-liu-xiang-3-ni93/
代码
class Solution {
public:
vector<vector<int>> v1,v2;
int minReorder(int n, vector<vector<int>>& connections) {
v1.resize(n);
v2.resize(n);
for(auto connection:connections)
{
v1[connection[0]].push_back(connection[1]);//正向建图
v2[connection[1]].push_back(connection[0]);//反向建图
}
vector<bool> vis(n,false);
queue<int> q;
q.push(0);
int cnt=0;
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=true;
for(int i=0;i<v1[x].size();i++)
if(!vis[v1[x][i]])
q.push(v1[x][i]);
for(int i=0;i<v2[x].size();i++)
{
if(!vis[v2[x][i]])
{
q.push(v2[x][i]);
cnt++;
}
}
}
return connections.size()-cnt;
}
};