0에서 n-1까지 번호가 매겨진 n개의 다른 도시가 있고 n-1개의 도로가 있어 두 개의 다른 도시 사이를 여행하는 방법은 단 하나라고 가정합니다. 교통부가 도로가 너무 좁아서 한 방향으로 방향을 지정하기로 결정했다고 가정해 보겠습니다.
여기서 도로는 연결[i] =[a, b]인 연결로 표시됩니다. 이는 도시에서 b까지의 도로를 나타냅니다.
수도(도시 번호 0)에 큰 행사가 있고 많은 사람들이 이 도시로 여행을 가고 싶어하는 경우. 각 도시가 도시 0을 방문할 수 있도록 일부 도로에서 방향 재지정 작업을 수행해야 합니다. 변경된 모서리의 최소 수를 찾아야 합니다.
따라서 입력이 6과 같으면 연결 =[[0,1],[1,3],[2,3],[4,0],[4,5]],
각 노드가 대문자에 도달할 수 있도록 빨간색으로 표시된 가장자리의 방향을 변경해야 하므로 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N =5*10^4 + 5
크기의 graph1, graph2 목록의 두 배열을 정의합니다. -
주요 방법에서 다음을 수행하십시오 -
-
하나의 지도 정의
-
e의 각 요소에 대해 수행
-
그래프1[it[0]]의 끝에 삽입[1]
-
그래프2[it[1]]의 끝에 삽입[0]
-
-
크기가 n인 배열 dist를 정의하고 N + 10으로 채웁니다.
-
ret :=0, in[0] :=0, dist[0] :=0
-
하나의 대기열 정의 q
-
q에 0 삽입
-
방문한 한 세트 정의
-
방문에 0 삽입
-
동안(q가 비어 있지 않음) -
를 수행합니다.-
node :=q의 첫 번째 요소
-
q에서 요소 삭제
-
ret :=ret + dist[노드]
-
graph2[node]의 각 요소에 대해 수행
-
방문하지 않고 dist[it]> 0이면 -
-
dist[it] :=0
-
q에 삽입
-
방문한 페이지에 삽입
-
-
-
graph1[node]의 각 요소에 대해 수행
-
방문하지 않고 dist[it]> 1이면 -
-
dist[it] :=1
-
q에 삽입
-
방문한 페이지에 삽입
-
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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