Monday, May 30, 2016

UVA 280 - Vertex Solution using C++ OOP Graph BFS to Find Connected Components and Unreachable nodes


Problem Link:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=216

Problem Explanation & Visalization:

TODO

Input & Output Explanation:

The first line of input is the number of nodes in graph. Next, multiple rows of graph linked list representation rows. The first number in the row is (u) current node and rest are (v) all the nodes connected with (u). Each row is terminated by 0.

After that there is another input (c) which is the number of nodes to input in order to perform BFS (or, your choice of algorithm) on them. Next, are given (c) inputs and perform BFS on all of them and print connected components count and unreachable nodes from current node.

Lastly, a zero on its own to represent end of all input groups.

Input & Output:

Input:
3 1 2 0 2 2 0 3 1 2 0 0 2 1 2 0

Output:
2 1 3 2 1 3
More input and output in udebug:
https://www.udebug.com/UVa/280

Code Vector Vector:



Code Vector List:

This code has slightly higher runtime than the code above.

No comments: