n সংখ্যক সিটি আছে (০ থেকে n-1) এবং n-1 রোড আছে যাতে যেকোনো দুটি সিটির মধ্যে একমাত্র পথ আছে। রোডগুলো একদিকনির্দেশ করা হয়েছে। কানেকশন [a,b] মানে সিটি a থেকে b এ রোড।
রাজধানী (সিটি ০) এ বড় ইভেন্ট হচ্ছে। সব সিটি থেকে সিটি ০ এ যাওয়া যাবে এমনভাবে কমপক্ষে কতটি রোডের দিক পরিবর্তন করতে হবে তা বের করতে হবে।
ইনপুট: n=6, connections=[[0,1],[1,3],[2,3],[4,0],[4,5]] → আউটপুট: 3
সমাধানের ধাপগুলো (BFS):
দুটি গ্রাফ
graph1(আউটগোইং) ওgraph2(ইনকামিং) বানাবdistঅ্যারে দিয়ে কস্ট ট্র্যাক করব (০ বা ১)সিটি ০ থেকে BFS শুরু করব
graph2(উল্টা এজ) কস্ট ০,graph1(সহজ এজ) কস্ট ১ভিজিটেড নোডে মিনিমাম কস্ট যোগ করব
উদাহরণ
নিচের কোডটি দেখুন −
#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;
}
};
int 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
