# Untitled

unknown
plain_text
22 days ago
2.7 kB
4
Indexable
Never
class Solution {

List<List<Integer>> adjList = new ArrayList();

// Iterate over each pair of routes and add an edge between them if there's a common stop.
void createGraph(int[][] routes) {
for (int i = 0; i < routes.length; i++) {
for (int j = i + 1; j < routes.length; j++) {
if (haveCommonNode(routes[i], routes[j])) {
adjList.get(i).add(j);
adjList.get(j).add(i);
}
}
}
}

// Returns true if the provided routes have a common stop, false otherwise.
boolean haveCommonNode(int[] route1, int[] route2) {
int i = 0, j = 0;
while (i < route1.length && j < route2.length) {
if (route1[i] == route2[j]) {
return true;
}

if (route1[i] < route2[j]) {
i++;
} else {
j++;
}
}
return false;
}

// Add all the routes in the queue that have the source as one of the stops.
void addStartingNodes(Queue<Integer> q, int[][] routes, int source) {
for (int i = 0; i < routes.length; i++) {
if (isStopExist(routes[i], source)) {
q.add(i);
}
}
}

// Returns true if the given stop is present in the route, false otherwise.
boolean isStopExist(int[] route, int stop) {
for (int j = 0; j < route.length; j++) {
if (route[j] == stop) {
return true;
}
}
return false;
}

public int numBusesToDestination(int[][] routes, int source, int target) {
if (source == target) {
return 0;
}

for (int i = 0; i < routes.length; ++i) {
Arrays.sort(routes[i]);
adjList.add(new ArrayList());
}

createGraph(routes);

Queue<Integer> q = new LinkedList<>();
addStartingNodes(q, routes, source);

Set<Integer> vis = new HashSet<Integer>(routes.length);
int busCount = 1;
while (!q.isEmpty()) {
int sz = q.size();

while (sz-- > 0) {
int node = q.remove();

// Return busCount, if the stop target is present in the current route.
if (isStopExist(routes[node], target)) {
return busCount;
}

// Add the adjacent routes.
for (int adj : adjList.get(node)) {
if (!vis.contains(adj)) {
vis.add(adj);
q.add(adj);
}
}
}

busCount++;
}

return -1;
}
}
Leave a Comment