Question:

How to check if undirected graph of nodes is a tree or not using Java

Summary

Here we are using an adjacency list representation for an undirected graph in order to check for the presence of cycles, a key characteristic of trees.

We will initialize an ArrayList of ArrayLists. This will represent the adjacency list of each vertex of the graph.

Solution

//User function Template for Java

class Solution {

public boolean isTree(int n, int m, ArrayList<ArrayList<Integer>> edges)

{

ArrayList<ArrayList<Integer>> adj=new ArrayList<>();

for(int i=0;i<n;i++){

adj.add(new ArrayList<>());

}

for(ArrayList<Integer> arr:edges){

int ele1=arr.get(0);

int ele2=arr.get(1);

adj.get(ele1).add(ele2);

adj.get(ele2).add(ele1);

}

int cnt=0;

int[] visited=new int[n];

for(int i=0;i<n;i++){

if(visited[i]==0){

cnt++;

if(loop(adj,visited,i,-1)){

return false;

}

return cnt>1?false:true;

}

boolean loop(ArrayList<ArrayList<Integer>> adj,int[] visited,int node,int par){

visited[node]=1;

for(int ele:adj.get(node)){

if(visited[ele]==0){

if(loop(adj,visited,ele,node)){

return true;

}

else if(ele!=par){

return true;

}

return false;

}

Explanation

Initialize a counter ‘cnt’ to count the number of connected components in the graph.
The visited vertices are recorded in the visited array.
If the component (tree) is the only one connected, return true; if not, return false.

>How to check whether string is palindrome or not using C++

>How to determine the smallest possible size of a vertex cover using C++

>Build an Electron application from scratch

>Building Web API using ASP.NET (C#)

>Built Web API using ASP.NET (C#)