Given a 2-D array A[][] of size N×3, where each element of the array consists of {x, y, r}, where x and y are coordinates of that circle and r is the radius of that circle, the task is to check all the circles form a single component where a component is the set of connected circles.
Note: Two circles are connected if they touch or intersect each other.
Examples:
Input: A[][] = {{0, 0, 2}, {0, 3, 3}, {0, 6, 1}, {1, 0, 1}}
Output: true
Explanation: All circles are connected to every other circle.Input: A[][] = {{0, 0, 1}, {0, 3, 1}, {0, 4, 1}, {1, 0, 1}}
Output: false
Explanation: Circles at index 0 and 3 form a single component
while circle 1 and 2 form separate component.
Since there are multiple components, the output is false.
Approach: The solution to the problem can be derived using the following idea
The idea is to construct a graph from the given input and check if corresponding vertices touch or intersect each other and in the end find that the graph forms a single connected component or not [i.e. if all the vertices can be visited starting from any vertex].
Following are the steps to implement the above approach:
- For every circle in A, find the distance between their centers.
- If the distance <= sum of radius
- connect both the vertices representing these circles
- If the distance <= sum of radius
- Perform a DFS from a single node on the graph.
- Now check in the visited array
- If there is any unvisited vertex, return false.
- Return true if there is no unvisited vertex.
Below is the code implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to create a graph from the// array of the circlesvector<vector<int> > constructGraph(int Arr[][3], int n){ vector<vector<int> > graph(n, vector<int>()); for (int u = 0; u < n; u++) { for (int v = u + 1; v < n; v++) { int x1 = Arr[u][0]; int y1 = Arr[u][1]; int r1 = Arr[u][2]; int x2 = Arr[v][0]; int y2 = Arr[v][1]; int r2 = Arr[v][2]; double dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); if (r1 + r2 >= dist) { graph[u].push_back(v); graph[v].push_back(u); } } } return graph;}// Function to perform DFS on the graphvoid dfsVisit(int v, vector<bool>& visited, vector<vector<int> > graph){ visited[v] = true; for (auto nbr : graph[v]) { if (!visited[nbr]) { dfsVisit(nbr, visited, graph); } }}// Function to check whether the// circle form a single component or notbool isSingleComponent(int arr[][3], int n){ vector<vector<int> > graph = constructGraph(arr, 4); vector<bool> visited(n, 0); dfsVisit(0, visited, graph); for (int i = 0; i < n; i++) { if (!visited[i]) return false; } return true;}int main(){ int A[][3] = { { 0, 0, 2 }, { 0, 3, 3 }, { 0, 6, 1 }, { 1, 0, 1 } }; // Function Call cout << (isSingleComponent(A, 4)) << endl; ;}// This code is contributed by garg28harsh. |
Java
// Java program to implement the approachimport java.util.*;public class GFG { // Function to create a graph from the // array of the circles static ArrayList<ArrayList<Integer> > constructGraph(int[][] Arr) { int n = Arr.length; ArrayList<ArrayList<Integer> > graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int u = 0; u < n; u++) { for (int v = u + 1; v < n; v++) { int x1 = Arr[u][0]; int y1 = Arr[u][1]; int r1 = Arr[u][2]; int x2 = Arr[v][0]; int y2 = Arr[v][1]; int r2 = Arr[v][2]; double dist = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); if (r1 + r2 >= dist) { graph.get(u).add(v); graph.get(v).add(u); } } } return graph; } // Function to perform DFS on the graph static void dfsVisit(int v, boolean[] visited, ArrayList<ArrayList<Integer> > graph) { visited[v] = true; for (Integer nbr : graph.get(v)) { if (!visited[nbr]) { dfsVisit(nbr, visited, graph); } } } // Function to check whether the // circle form a single component or not static boolean isSingleComponent(int[][] arr) { int n = arr.length; ArrayList<ArrayList<Integer> > graph = constructGraph(arr); boolean[] visited = new boolean[n]; dfsVisit(0, visited, graph); for (int i = 0; i < n; i++) { if (!visited[i]) return false; } return true; } // Driver Code public static void main(String[] args) { int A[][] = { { 0, 0, 2 }, { 0, 3, 3 }, { 0, 6, 1 }, { 1, 0, 1 } }; // Function Call System.out.println(isSingleComponent(A)); }} |
Python3
import mathclass GFG : # Function to create a graph from the # array of the circles @staticmethod def constructGraph( Arr) : n = len(Arr) graph = [] i = 0 while (i < n) : graph.append( []) i += 1 u = 0 while (u < n) : v = u + 1 while (v < n) : x1 = Arr[u][0] y1 = Arr[u][1] r1 = Arr[u][2] x2 = Arr[v][0] y2 = Arr[v][1] r2 = Arr[v][2] dist = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) if (r1 + r2 >= dist) : graph[u].append(v) graph[v].append(u) v += 1 u += 1 return graph # Function to perform DFS on the graph @staticmethod def dfsVisit( v, visited, graph) : visited[v] = True for nbr in graph[v] : if (not visited[nbr]) : GFG.dfsVisit(nbr, visited, graph) # Function to check whether the # circle form a single component or not @staticmethod def isSingleComponent( arr) : n = len(arr) graph = GFG.constructGraph(arr) visited = [False] * (n) GFG.dfsVisit(0, visited, graph) i = 0 while (i < n) : if (not visited[i]) : return False i += 1 return True # Driver Code @staticmethod def main( args) : A = [[0, 0, 2], [0, 3, 3], [0, 6, 1], [1, 0, 1]] # Function Call print(GFG.isSingleComponent(A)) if __name__=="__main__": GFG.main([]) # This code is contributed by aaityaburujwale. |
C#
using System;using System.Collections.Generic;class GFG{ // Function to create a graph from the // array of the circles static List<int>[] ConstructGraph(int[][] arr) { int n = arr.Length; var graph = new List<int>[ n ]; for (int i = 0; i < n; i++) { graph[i] = new List<int>(); } for (int u = 0; u < n; u++) { for (int v = u + 1; v < n; v++) { int x1 = arr[u][0]; int y1 = arr[u][1]; int r1 = arr[u][2]; int x2 = arr[v][0]; int y2 = arr[v][1]; int r2 = arr[v][2]; double dist = Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); if (r1 + r2 >= dist) { graph[u].Add(v); graph[v].Add(u); } } } return graph; } // Function to perform DFS on the graph static void DfsVisit(int v, bool[] visited, List<int>[] graph) { visited[v] = true; foreach(int nbr in graph[v]) { if (!visited[nbr]) { DfsVisit(nbr, visited, graph); } } } // Function to check whether the // circle form a single component or not static bool IsSingleComponent(int[][] arr) { int n = arr.Length; var graph = ConstructGraph(arr); var visited = new bool[n]; DfsVisit(0, visited, graph); for (int i = 0; i < n; i++) { if (!visited[i]) { return false; } } return true; } // Driver code static void Main(string[] args) { int[][] arr = { new[] { 0, 0, 2 }, new[] { 0, 3, 3 }, new[] { 0, 6, 1 }, new[] { 1, 0, 1 } }; // Function call Console.WriteLine(IsSingleComponent(arr)); }}// This code is contributed by divyansh2212 |
Javascript
// Javascript program to implement the approach// Function to create a graph from the// array of the circlesfunction constructGraph(Arr, n) { let graph = new Array(n); for (let i = 0; i < n; i++) graph[i] = []; for (let u = 0; u < n; u++) { for (let v = u + 1; v < n; v++) { let x1 = Arr[u][0]; let y1 = Arr[u][1]; let r1 = Arr[u][2]; let x2 = Arr[v][0]; let y2 = Arr[v][1]; let r2 = Arr[v][2]; let dist = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); if (r1 + r2 >= dist) { graph[u].push(v); graph[v].push(u); } } } return graph;}// Function to perform DFS on the graphfunction dfsVisit(v, visited, graph) { visited[v] = true; for (let nbr of graph[v]) { if (!visited[nbr]) { dfsVisit(nbr, visited, graph); } }}// Function to check whether the// circle form a single component or notfunction isSingleComponent(arr, n) { let graph = constructGraph(arr, 4); let visited = new Array(n); for (let i = 0; i < n; i++) visited[i] = 0; dfsVisit(0, visited, graph); for (let i = 0; i < n; i++) { if (!visited[i]) return false; } return true;}let A = [ [0, 0, 2], [0, 3, 3], [0, 6, 1], [1, 0, 1],];// Function Callconsole.log(isSingleComponent(A, 4));// This code is contributed by ishankhandelwals. |
Output
true
Time Complexity: O(N2), since we are using two loops to traverse all the elements in the given array hence the time taken is quadratic
Auxiliary Space: O(N2), since we are creating an extra graph of size n*n so the space takes is quadratic
