주어진 트리 그래프가 C++에서 선형인지 아닌지 확인

트리 그래프가 선형인지 아닌지 확인하는 방법을 알아보겠습니다. 선형 트리 그래프는 선형 트리 그래프의 예라고 가정해 한 줄로 표현할 수 있습니다.

그러나 이것은 선형이 아닙니다 -

그래프가 선형인지 아닌지 확인하기 위해 두 가지 조건을 따를 수 있습니다.

• 노드 수가 1이면 트리 그래프가 선형입니다.
• 만약 (n – 2) 노드의 차수가 2인 경우

예시

#include <iostream>
#include <vector>
#define N 4
using namespace std;
class Graph{
   private:
   int V;
   vector<int> *adj;
   public:
   Graph(int v){
      V = v;
      adj = new vector<int>[v];
   }
   void addEdge(int u, int v){
      adj[u].push_back(v);
      adj[v].push_back(u);
   }
   bool 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;
   }
};
int main() {
   Graph g1(3);
   g1.addEdge(0, 1);
   g1.addEdge(0, 2);
   if (g1.isLinear())
      cout << "The graph is linear";
   else
      cout << "The graph is not linear";
}

출력

The graph is linear