My solution without using graph traversal


  • 0
    P

    I just determined whether the graph is a tree by

    1. whether it has correct number of edges

    2. whether it has any isolated edge(when n >2)

    3. whether it has any isolated vertex(when n > 1)

      Not sure if my strategy is correct. But this strategy passed the test

      Would really appreciate if anyone could find an exception. Thanks!!

      class Solution {
      public:
      bool validTree(int n, vector<pair<int, int>>& edges) {
      if (edges.size() != n-1) return false;
      int vertexes[n];
      fill_n(vertexes, n, 0);
      for (pair<int, int> &e : edges) {
      vertexes[e.first] ++;
      vertexes[e.second] ++;
      }
      /* Check if the graph has any isolated edge /
      for (pair<int, int> &e : edges) {
      if (vertexes[e.first] == 1 && vertexes[e.second] == 1 && n > 2) {
      return false;
      }
      }
      /
      Check if the graph has any isolated vertex */
      for (int v = 0; v < n; v++) {
      if (vertexes[v] == 0 && n != 1) return false;
      }
      return true;
      }
      };


  • 1

    Not sure if my strategy is correct. But this strategy passed the test
    Would really appreciate if anyone could find an exception.

    Here's one:

    n = 6;
    edges = {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}};


  • 0

    Thanks Stefan. I have just added this test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.