LC.191.5426. 重新规划路线 (BFS&DFS)weixin45750972的博客-

LC.191.5426. 重新规划路线(BFS&DFS)

传送门
思路：1.建立反图DFS，先用从0开始进行反图DFS，反图能走的路不用修改。然后再对正图进行DFS，用正图每遍历到一个点答案+1，就可以。
2.BFS，因为是一棵树，最后肯定是以0为根的形状，然后用一个二维数组存一下每个结点所在的编号，从0开始遍历，若有不能到达的，就答案加1，然后入队，继续BFS。
3.先对边集从小到大排，然后用并查集判断当前边终点是否在集合内，在就加入起点，否则答案+1，加入终点。

方法1代码:

const int N=5e4+5; class Solution { public:     vector<int>e[N];     vector<int>fe[N]; bool vis[N]; int ans; void dfs(int u){ for(auto v:fe[u]){ if(!vis[v]) vis[v]=1,dfs(v); } for(auto v:e[u]){ if(!vis[v]) ans++,vis[v]=1,dfs(v); } } int minReorder(int n, vector<vector<int>>& p) { for(auto it:p){ int u=it[0],v=it[1];                e[u].push_back(v);                fe[v].push_back(u); }           vis[0]=1; dfs(0); return ans; } }; 

方法2代码：

class Solution{ public: int minReorder(int n, vector<vector<int>>& p) {         vector<vector<int>> id(n, vector<int>()); for (int i = 0; i < n-1; i++) {             id[p[i][0]].push_back(i);             id[p[i][1]].push_back(i); }         vector<bool>vis(n, 0); int ans = 0;         queue<int>q;         q.push(0); while (!q.empty()) { int u= q.front();             q.pop(); for (auto it: id[u]) { if (vis[it]) continue;                 vis[it] = true; int x=p[it][0],y=p[it][1];                 ans+=(x==u);                 x=(x==u)?y:x;                 q.push(x); } } return ans; } }; 

方法3：

class Solution { public: int minReorder(int n, vector<vector<int>>& p) {          set<int>s;          s.insert(0); int ans=0; sort(p.begin(),p.end(),cmp); for(auto a:p){ if(s.count(a[1])) s.insert(a[0]); else ans++,s.insert(a[1]); } return ans; } private: static bool cmp(vector<int> &a,vector<int> &b){ int x=min(a[0],a[1]),y=min(b[0],b[1]); return x<y; } };