I’m working on Milk Factory, and trying to do it with BFS(find all nodes each one can visit and the lowest common one) but it doesn’t work. I tested everything else, it’s the BFS that seems to be failing. I’ve been looking at it for hours now and can’t see what’s wrong. Please help me out
I’m working on Milk Factory, and trying to do it with BFS(find all nodes each one can visit and the lowest common one) but it doesn’t work. I tested everything else, it’s the BFS that seems to be failing. I’ve been looking at it for hours now and can’t see what’s wrong. Please help me out
#include <bits/stdc++.h>
using namespace std;
int main(){
//freopen("factory.in", "r", stdin);
//freopen("factory.out", "w", stdout);
int N, hold, hold2;
cin >> N;
vector<vector<int>> adjList(N);
for(int a = 0; a < N - 1; a++) {
cin >> `Preformatted text`hold >> hold2;
adjList[hold - 1].push_back(hold2 - 1);
}
vector<bool> totalVisit(N);
for(int a =0 ;a < N; a++) totalVisit[a] = 1;
for(int a =0; a < N; a++){
vector<bool> visited(N);
for(int c =0 ;c < N; c++) visited[c] = 0;
queue<int> myQueue;
myQueue.push(a);
while(myQueue.size() > 0){
int temp = myQueue.front();
myQueue.pop();
//cout << temp;
if(!visited[temp]){
for(auto adj : adjList[temp]){
if(!visited[adj]){
myQueue.push(adj);
visited[adj] = 1;
}
}
}
visited[temp] = 1 ;
}
for(int b = 0; b < N; b++){
//cout << visited[b];
totalVisit[b] = min(totalVisit[b], visited[b]);
}
cout << endl;
}
for(int a =0; a < N; a++){
if(totalVisit[a]){
cout << a + 1;
break;
}
if( a== N - 1 && totalVisit[a] != 1){
cout << - 1;
break;
}
}
return 0;
}