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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: http://quickgrid.blogspot.com | |
| * Solution: vector of vector oop graph representation and operation. | |
| * Task: Input directed graph, find out connected component count, | |
| * print out unreachable nodes. | |
| * Note: Input node is from 1 to 100. So, here it is 0 to 99 to | |
| * keep it simple. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| // The whole graph structure look at my graph | |
| // related posts for visualization of this structure. | |
| class Graph{ | |
| private: | |
| int V; | |
| int connectedComponentsCount; | |
| vector< vector<int> > adjList; | |
| public: | |
| Graph(int V); | |
| void addEdge(int u, int v); | |
| void BFS(int s); | |
| }; | |
| Graph::Graph(int V){ | |
| this->V = V; | |
| adjList.resize(V); | |
| } | |
| // Since start node is from 0 in current structure. | |
| // So, 1 is turned into 0 here. | |
| void Graph::addEdge(int u, int v){ | |
| adjList[u - 1].push_back(v - 1); | |
| } | |
| // BFS Algorithm | |
| void Graph::BFS(int s){ | |
| // Initialize an array with all nodes unvisited. | |
| bool *visited = new bool[V]; | |
| for(int v = 0; v < V; ++v){ | |
| visited[v] = false; | |
| } | |
| // Insert the given node to run BFS. | |
| queue<int> Q; | |
| Q.push(s); | |
| // Get the front of the queue and check all its adjacent nodes if | |
| // they were visited. If not mark them visited and push the unvisited | |
| // node to the queue. | |
| int node; | |
| while(!Q.empty()){ | |
| node = Q.front(); | |
| Q.pop(); | |
| for(int v = 0; v < adjList[node].size(); ++v){ | |
| if( !visited[ adjList[node][v] ] ){ | |
| visited[ adjList[node][v] ] = true; | |
| Q.push( adjList[node][v] ); | |
| } | |
| } | |
| } | |
| // Count the number of connected components in graph and print. | |
| int connectedComponentsCount = 0; | |
| for(int v = 0; v < V; ++v){ | |
| if(!visited[v]) | |
| connectedComponentsCount++; | |
| } | |
| printf("%d", connectedComponentsCount); | |
| // Print all the unreachable nodes from the given node. Since, BFS | |
| // on the start node already filled up the array now just print all | |
| // the unvisited node. | |
| for(int v = 0; v < V; ++v){ | |
| if(!visited[v]) | |
| printf(" %d", v + 1); | |
| } | |
| printf("\n"); | |
| } | |
| int main(){ | |
| // Create the graph in given linked list format. | |
| int n; | |
| while( scanf("%d", &n) && n ){ | |
| // Initialize the new graph with node count. | |
| Graph *g = new Graph(n); | |
| // Connect node u with given v nodes to create an edge. | |
| int u,v; | |
| while( scanf("%d", &u) && u ){ | |
| while( scanf("%d", &v) && v ){ | |
| g->addEdge(u,v); | |
| } | |
| } | |
| // Take input of the nodes where to run the custom BFS algorithm. | |
| int c, node; | |
| scanf("%d", &c); | |
| for(int i = 0; i < c; ++i){ | |
| scanf("%d", &node); | |
| g->BFS(node - 1); | |
| } | |
| } | |
| return 0; | |
| } |
Code Vector List:
This code has slightly higher runtime than the code above.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: http://quickgrid.blogspot.com | |
| * Solution: vector of list oop graph representation and operation. | |
| * Task: Input directed graph, find out connected component count, | |
| * print out unreachable nodes. | |
| * Note: Input node is from 1 to 100. So, here it is 0 to 99 to | |
| * keep it simple. | |
| */ | |
| #include<bits/stdc++.h> | |
| using namespace std; | |
| // The adjacency list is now vector of list. | |
| class Graph{ | |
| private: | |
| int V; | |
| int connectedComponentsCount; | |
| vector< list<int> > adjList; | |
| public: | |
| Graph(int V); | |
| void addEdge(int u, int v); | |
| void BFS(int s); | |
| }; | |
| Graph::Graph(int V){ | |
| this->V = V; | |
| adjList.resize(V); | |
| } | |
| void Graph::addEdge(int u, int v){ | |
| adjList[u - 1].push_back(v - 1); | |
| } | |
| void Graph::BFS(int s){ | |
| bool *visited = new bool[V]; | |
| for(int v = 0; v < V; ++v){ | |
| visited[v] = false; | |
| } | |
| queue<int> Q; | |
| Q.push(s); | |
| int node; | |
| while(!Q.empty()){ | |
| node = Q.front(); | |
| Q.pop(); | |
| // Only change here to iterate the current node and see if its | |
| // connected nodes are visited or not. | |
| list<int>::iterator it; | |
| for( it = adjList[node].begin(); it != adjList[node].end(); ++it ){ | |
| if( !visited[ *it ] ){ | |
| visited[ *it ] = true; | |
| Q.push( *it ); | |
| } | |
| } | |
| } | |
| int connectedComponentsCount = 0; | |
| for(int v = 0; v < V; ++v){ | |
| if(!visited[v]) | |
| ++connectedComponentsCount; | |
| } | |
| printf("%d", connectedComponentsCount); | |
| for(int v = 0; v < V; ++v){ | |
| if(!visited[v]) | |
| printf(" %d", v + 1); | |
| } | |
| printf("\n"); | |
| } | |
| int main(){ | |
| // | |
| //freopen("input.txt", "r", stdin); | |
| //freopen("output.txt", "w", stdout); | |
| // | |
| int n; | |
| while( scanf("%d", &n) && n ){ | |
| // Create a graph given in the above diagram | |
| Graph *g = new Graph(n); | |
| int u,v; | |
| while( scanf("%d", &u) && u ){ | |
| while( scanf("%d", &v) && v ){ | |
| g->addEdge(u,v); | |
| } | |
| } | |
| int c, node; | |
| scanf("%d", &c); | |
| for(int i = 0; i < c; ++i){ | |
| scanf("%d", &node); | |
| g->BFS(node - 1); | |
| } | |
| } | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment