Islands

 

An island is a small piece of land surrounded by water . A group of islands is said to be connected if we can reach from any given island to any other island in the same group . Given V islands (numbered from 0 to V-1) and E connections or edges between islands. Can you count the number of connected groups of islands.

Input Format :
The first line of input contains two integers, that denote the value of V and E.
Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b.
Output Format :
Print the count the number of connected groups of islands
Constraints :
0 <= V <= 1000
0 <= E <= (V * (V-1)) / 2
0 <= a <= V - 1
0 <= b <= V - 1
Time Limit: 1 second
Sample Input 1:
5 8
0 1
0 4
1 2
2 0
2 4
3 0
3 2
4 3
Sample Output 1:
1 


#include <iostream>
using namespace std;

int main() {
    // Write your code here
}

Comments

Post a Comment

Popular posts from this blog

Coding Ninjas

  Given a NxM matrix containing Uppercase English Alphabets only. Your task is to tell if there is a path in the given matrix which makes the sentence “CODINGNINJA” . There is a path from any cell to all its neighbouring cells. For a particular cell, neighbouring cells are those cells that share an edge or a corner with the cell. Input Format : The first line of input contains two space separated integers N and M, where N is number of rows and M is the number of columns in the matrix. Each of the following N lines contain M characters. Please note that characters are not space separated. Output Format : Print 1 if there is a path which makes the sentence “CODINGNINJA” else print 0. Constraints : 1 <= N <= 1000 1 <= M <= 1000 Time Limit: 1 second Sample Input 1: 2 11 CXDXNXNXNXA XOXIXGXIXJX Sample Output 1: 1 bool hasPath ( vector < vector < char >> & board , int n , int m ) { // Write your code here. } #include < iostream > #include ...
Read more

Code : Get Path - BFS

  Given an undirected graph G(V, E) and two vertices v1 and v2 (as integers), find and print the path from v1 to v2 (if exists). Print nothing if there is no path between v1 and v2. Find the path using BFS and print the shortest path available. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. 3. Print the path in reverse order. That is, print v2 first, then intermediate vertices and v1 at last. 4. Save the input graph in Adjacency Matrix. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b. The following line contain two integers, that denote the value of v1 and v2. Output Format : Print the path from v1 to v2 in reverse order. Constraints : 2 <= V <= 1000 1 <= E <= (V * (V - 1)) / 2 0 <= a <= V - 1 0 <= b <...
Read more

Code : Is Connected ?

  Given an undirected graph G(V,E), check if the graph G is connected graph or not. Note: 1. V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 2. E is the number of edges present in graph G. Input Format : The first line of input contains two integers, that denote the value of V and E. Each of the following E lines contains two integers, that denote that there exists an edge between vertex a and b. Output Format : The first and only line of output contains "true" if the given graph is connected or "false", otherwise. Constraints : 0 <= V <= 1000 0 <= E <= (V * (V - 1)) / 2 0 <= a <= V - 1 0 <= b <= V - 1 Time Limit: 1 second Sample Input 1: 4 4 0 1 0 3 1 2 2 3 Sample Output 1: true Sample Input 2: 4 3 0 1 1 3 0 3 Sample Output 2: false Sample Output 2 Explanation The graph is not connected, even though vertices 0,1 and 3 are connected to each other but there isn’t any path from vertices 0,1,3 to vertex...
Read more