Monday, May 30, 2016
UVA 280 - Vertex Solution using C++ OOP Graph BFS to Find Connected Components and Unreachable nodes
May 30, 2016
280 vertex
,
beginner
,
bfs
,
c++
,
connected components
,
easy problem
,
explanation
,
freopen
,
list iterator
,
oop graph
,
queue
,
solution
,
stl
,
unreachable nodes
,
uva
,
vector list
Problem Link:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=216Problem Explanation & Visalization:
TODOInput & 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/280Code Vector Vector:
Code Vector List:
This code has slightly higher runtime than the code above.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment