C++ Code for WebPages (TCS Codevita) | PrepInsta

November 8, 2023

WebPages

TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. WebPages is one of the sample problem of this year TCS CodeVita season 11 competition.

Question -: Consider a set of web pages, numbered from 1 to N. Each web page has links to one or more web pages. Clicking on a link in a page, takes one to the other web page. You are provided numbers of two web pages viz, starting web page and end web page. Your task is to find the minimum number of clicks required to reach the end page from the start page. If end page cannot be reached from start page, print -1 as the output. For better understanding refer Examples section.

Constraints

0 < N <= 100

0 < L < 10

Input

First line contains an integer N denoting number of web pages.

Next N lines contain L space separated integers depicting linked webpage number(s) from that webpage

Output

Print the minimum number of clicks required to open the end page from start page. If not possible, print -1 as output.

Time Limit (secs)

Example 1

Input

2 4

1 5

2 3

Output

Explanation:

First line conveys that there is total 5 pages.

Second line conveys that there are links from page 1 to pages 2 and 4.

Third line conveys that there is a link from page 2 to page 1.

Fourth line conveys that there are links from page 3 to pages 1 and 5.

Fifth line conveys that there are links from page 4 to pages 2 and 3.

Sixth line conveys that there is a links from page 5 to page 5 itself.

Seventh line conveys that starting page is 2 and ending page is 3

From page 2, we can open only page 1. From page 1, we can open page 4. From page 4, we can open page 3. So, minimum 3 clicks are required, and this is the output.

Example 2

Input

2 3

Output

-1

Explanation:

First line conveys that there is total 3 pages.

Second line conveys that there are links from page 1 to page 2.

Third line conveys that there is a link from page 2 to page 1.

Fourth line conveys that there are links from page 3 to page 1.

Since there is no way to reach from page 2 to page 3, print -1 as output.

C++

Run

#include < iostream>
#include < vector>
#include < queue>
using namespace std;

int find_min_clicks(int N, vector>& pages, int start, int end) {
	vector visited(N + 1, false);
	queue> q;
	q.push({start, 0});

	while (!q.empty()) {
    	int current_page = q.front().first;
    	int clicks = q.front().second;
    	q.pop();
    	visited[current_page] = true;

    	if (current_page == end) {
        	return clicks;
    	}

    	for (int linked_page : pages[current_page]) {
        	if (!visited[linked_page]) {
            	q.push({linked_page, clicks + 1});
        	}
    	}
	}

	return -1;
}

int main() {
	int N;
	cin >> N;
	vector> pages(N + 1);

	for (int i = 1; i <= N; i++) {
    	int num_links;
    	cin >> num_links;
    	pages[i].resize(num_links);

    	for (int j = 0; j < num_links; j++) {
        	cin >> pages[i][j];
    	}
	}

	int start, end;
	cin >> start >> end;

	int result = find_min_clicks(N, pages, start, end);
	cout << result << endl;

	return 0;
}