Given a tree check if it is linear or not.
1 / \ 2 3 Linear as we can form a line 2 1 3
1
/ \
2 3
/ \
4 5
Not linear
Examples:
Input : 3 1 2 1 3 Output : YES Explanation: The Tree formed is 2-1-3 which is a linear one. Input : 4 1 2 2 3 4 2 Output : NO
Approach: The given tree would be linear only if n-2 of its nodes have indegree == 2 or number of nodes, n==1.
Implementation:
C++
// A C++ program to check whether a graph is // Linear or not#include<bits/stdc++.h>using namespace std;// This class represents a undirected graph // using adjacency list representationclass Graph{ public: // No. of vertices int V; // Constructor Graph(int v) { V = v; } // Function to add an edge into the graph void addEdge(vector<int> adj[], int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } // Returns true if the graph is linear, // else false. bool isLinear(vector<int> adj[]) { // If the number of vertice is 1 then // the tree is always Linear if (V == 1) return true; int count = 0; // Counting the number of vertices // with indegree 2 for(int i = 0; i < V; i++) { if (adj[i].size() == 2) count++; } if (count == V - 2) return true; else return false; }};// Driver codeint main(){ // Create a graph given in the // above example Graph g1(3); vector<int> adj[g1.V]; g1.addEdge(adj, 0, 1); g1.addEdge(adj, 0, 2); if (g1.isLinear(adj)) cout << "YES"; else cout << "NO"; return 0;}// This code is contributed by pratham76 |
Java
// A Java Program to check whether a graph is // Linear or notimport java.io.*;import java.util.*;// This class represents a undirected graph // using adjacency list representationclass Graph { private int V; // No. of vertices // Adjacency List private LinkedList<Integer> adj[]; // Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList<Integer>(); } // Function to add an edge into the graph void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } // Returns true if the graph is linear, // else false. boolean isLinear() { // If the number of vertice is 1 then // the tree is always Linear if (V == 1) return true; int count = 0; // Counting the number of vertices // with indegree 2 for (int i = 0; i < V; i++) { if (adj[i].size() == 2) count++; } if (count == V - 2) return true; else return false; } // Driver method public static void main(String args[]) { // Create a graph given in the above example 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"); }} |
Python3
# A Python3 Program to check whether a # graph is Linear or not # This class represents a undirected # graph using adjacency list representationclass Graph: def __init__(self, v): # No. of vertices self.V = v # Adjacency List self.adj = [[] for i in range(v)] # Function to add an edge into # the graph def addEdge(self, v, w): self.adj[v].append(w) self.adj[w].append(v) # Returns true if the graph is # linear, else false. def isLinear(self): # If the number of vertice is # 1 then the tree is always Linear if (self.V == 1): return True count = 0 # Counting the number of vertices # with indegree 2 for i in range(self.V): if (len(self.adj[i]) == 2): count += 1 if (count == self.V - 2): return True else: return False # Driver codeif __name__=='__main__': # Create a graph given in the # above example g1 = Graph(3) g1.addEdge(0, 1) g1.addEdge(0, 2) if (g1.isLinear()): print("YES") else: print("NO") # This code is contributed by rutvik_56 |
C#
// A C# Program to check whether a graph is // Linear or notusing System;using System.Collections.Generic;// This class represents a undirected graph // using adjacency list representationpublic class Graph { private int V; // No. of vertices // Adjacency List private List<int> []adj; // Constructor Graph(int v) { V = v; adj = new List<int>[v]; for (int i = 0; i < v; ++i) adj[i] = new List<int>(); } // Function to add an edge into the graph void addEdge(int v, int w) { adj[v].Add(w); adj[w].Add(v); } // Returns true if the graph is linear, // else false. bool isLinear() { // If the number of vertice is 1 then // the tree is always Linear if (V == 1) return true; int count = 0; // Counting the number of vertices // with indegree 2 for (int i = 0; i < V; i++) { if (adj[i].Count == 2) count++; } if (count == V - 2) return true; else return false; } // Driver Code public static void Main(String []args) { // Create a graph given in the above example Graph g1 = new Graph(3); g1.addEdge(0, 1); g1.addEdge(0, 2); if (g1.isLinear()) Console.WriteLine("YES"); else Console.WriteLine("NO"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// A Javascript program to check // whether a graph is Linear or notlet V;let adj;// Function to add an edge into the graphfunction addEdge(v, w){ adj[v].push(w); adj[w].push(v);}// Returns true if the graph is linear,// else false.function isLinear(){ // If the number of vertice is 1 then // the tree is always Linear if (V == 1) return true; let count = 0; // Counting the number of vertices // with indegree 2 for(let i = 0; i < V; i++) { if (adj[i].length == 2) count++; } if (count == V - 2) return true; else return false;}// Driver code// Create a graph given in the above exampleV = 3;adj = new Array(V)for(let i = 0; i < V; ++i) adj[i] = []; addEdge(0, 1);addEdge(0, 2);if (isLinear()) document.write("YES");else document.write("NO");// This code is contributed by suresh07</script> |
Output
YES
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you will find 82264 additional Information on that Topic: geeksforgeeks.org/check-if-a-given-tree-graph-is-linear-or-not/ […]
… [Trackback]
[…] There you will find 61123 more Information to that Topic: geeksforgeeks.org/check-if-a-given-tree-graph-is-linear-or-not/ […]