ルートを並べ替えて、すべてのパスがC++でCityZeroにつながるようにします

0からn-1までの番号が付けられたnの異なる都市があり、2つの異なる都市間を移動する方法が1つしかないようにn-1の道路もあるとします。運輸省が道路が狭すぎるために道路を一方向に向けることを決定したとします。

ここで、道路は、connections [i] =[a、b]の接続で表されます。これは、都市aからbへの道路を表します。

首都（都市番号0）で大きなイベントがあり、多くの人がこの都市に旅行したい場合。各都市が都市0を訪問できるように、いくつかの道路で方向転換タスクを実行する必要があります。変更されたエッジの最小数を見つける必要があります。

したがって、入力が6のような場合、接続=[[0,1]、[1,3]、[2,3]、[4,0]、[4,5]]、

各ノードが首都に到達できるように、赤で表示されるエッジの方向を変更する必要があるため、出力は3になります。

これを解決するには、次の手順に従います-

• サイズN=5 * 10 ^ 4 + 5

  のリストgraph1、graph2の2つの配列を定義します。

• メインの方法から、次のようにします-

• で1つのマップを定義する

• eの要素ごとに、実行します

  • グラフ1[it[0]]

    の最後にit[1]を挿入します

  • グラフ2[it[1]]

    の最後にit[0]を挿入します

• サイズnの配列distを定義し、これをN+10で埋めます

• ret：=0、in [0]：=0、dist [0]：=0

• 1つのキューを定義するq

• qに0を挿入

• 訪問した1セットを定義する

• 訪問済みに0を挿入

• （qが空ではない）間、-

  • node：=qの最初の要素

  • qから要素を削除

  • ret：=ret + dist [node]

  • グラフ2[ノード]の要素ごとに、実行

    • 訪問されておらず、dist [it]> 0の場合、-

      • dist [it]：=0

      • qに挿入

      • 訪問済みに挿入

  • グラフ1[ノード]の要素ごとに、実行

    • 訪問されておらず、dist [it]> 1の場合、-

      • dist [it]：=1

      • qに挿入

      • 訪問済みに挿入

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
class Solution {
public:
   vector<int> graph1[N];
   vector<int> graph2[N];
   int minReorder(int n, vector<vector<int> >& e){
      map<int, int> in;
      for (auto& it : e) {
         graph1[it[0]].push_back(it[1]);
         graph2[it[1]].push_back(it[0]);
      }
      vector<int> dist(n, N + 10);
      int ret = 0;
      in[0] = 0;
      dist[0] = 0;
      queue<int> q;
      q.push(0);
      set<int> visited;
      visited.insert(0);
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         ret += dist[node];
         for (auto& it : graph2[node]) {
            if (!visited.count(it) && dist[it] > 0) {
               dist[it] = 0;
               q.push(it);
               visited.insert(it);
            }
         }
         for (auto& it : graph1[node]) {
            if (!visited.count(it) && dist[it] > 1) {
               dist[it] = 1;
               q.push(it);
               visited.insert(it);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}};
   cout << (ob.minReorder(6,v));
}

入力

6,{{0,1},{1,3},{2,3},{4,0},{4,5}}

出力

3