Check if a given tree graph is linear or not
import java.io.*;
import java.util.*;
class Graph {
private int V; // No. of vertices
private LinkedList<Integer> adj[];
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<Integer>();
}
void addEdge(int v, int w)
{
adj[v].add(w);
adj[w].add(v);
}
boolean isLinear()
{
if (V == 1)
return true;
int count = 0;
for (int i = 0; i < V; i++) {
if (adj[i].size() == 2)
count++;
}
if (count == V - 2)
return true;
else
return false;
}
public static void main(String args[])
{
Graph g1 = new Graph(3);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
if (g1.isLinear())
System.out.println("YES");
else
System.out.println("NO");
}
}
Suggested Creators