मान लीजिए n अलग-अलग शहर हैं जो 0 से n-1 तक नंबर किए गए हैं और n-1 सड़कें भी हैं जैसे कि दो अलग-अलग शहरों के बीच यात्रा करने का केवल एक ही रास्ता है। मान लीजिए परिवहन मंत्रालय ने सड़कों को एक दिशा में ओरिएंट करने का फैसला किया क्योंकि वे बहुत संकरी हैं।
यहाँ सड़कों को connections द्वारा दर्शाया गया है जहां connections[i] = [a, b] यह शहर a से b तक एक सड़क दर्शाता है।
यदि राजधानी (शहर नंबर 0) में एक बड़ा आयोजन है, और कई लोग इस शहर की यात्रा करना चाहते हैं। हमें कुछ सड़कों पर रीऑरिएंटिंग कार्य करना है जैसे कि प्रत्येक शहर शहर 0 तक जा सके। हमें बदले गए एज की न्यूनतम संख्या ढूंढनी है।
इसलिए, यदि इनपुट है 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]],
तो आउटपुट 3 होगा, क्योंकि हमें लाल रंग में दिखाए गए एज की दिशा बदलनी होगी जैसे कि प्रत्येक नोड राजधानी तक पहुंच सके।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
N = 5*10^4 + 5 आकार के दो ऐरे ऑफ लिस्ट graph1, graph2 परिभाषित करें
मुख्य विधि से निम्न करें -
एक मैप in परिभाषित करें
e के प्रत्येक एलिमेंट it के लिए, करें
it[1] को graph1[it[0]] के अंत में डालें
it[0] को graph2[it[1]] के अंत में डालें
n आकार का एक ऐरे dist परिभाषित करें और इसे N + 10 से भरें
ret := 0, in[0] := 0, dist[0] := 0
एक क्यू q परिभाषित करें
0 को q में डालें
एक सेट visited परिभाषित करें
0 को visited में डालें
जब (q खाली नहीं है), करें -
node := q का पहला एलिमेंट
q से एलिमेंट हटाएं
ret := ret + dist[node]
graph2[node] के प्रत्येक एलिमेंट it के लिए, करें
यदि it visited नहीं है और dist[it] > 0, तो -
dist[it] := 0
it को q में डालें
it को visited में डालें
graph1[node] के प्रत्येक एलिमेंट it के लिए, करें
यदि it visited नहीं है और dist[it] > 1, तो -
dist[it] := 1
it को q में डालें
it को visited में डालें
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
