Is it a Tree? (Editorial)

A graph with $n$ vertices is a tree if and only if:

The graph is connected. Start a depth-first search from the first vertex. Count the number of visited vertices during the search. If it equals $n$ , then the graph is connected.
$∣ V ∣ = ∣ E ∣ + 1$ |V| = |E| + 1. If the graph is a tree, then it contains $n - 1$ n - 1 edges
The graph does not contain cycles. Start a depth-first search from the first vertex. If a back edge exists, then the graph has a cycle and is not a tree.

Satisfying conditions $1)$ and $2)$ or $1)$ and $3)$ is sufficient for the graph to be a tree.

Example

The graph provided in the example is a tree.

Algorithm implementation — checking the conditions 1) and 3)

Declare the adjacency matrix of the graph $g$ and the array $u se d$ .

#define MAX 110
int g[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is $p$ . If a cycle is detected, the $f l a g$ variable is set to $1$ .

void dfs(int v, int p)
{

If the graph is no longer a tree $(f l a g = 1)$ (flag = 1), there is no need to continue the search.

  if (flag) return;

Mark the vertex $v$ as visited.

  used[v] = 1;

The vertex $v$ is visited, increase $c$ by $1$ .

  c++;

The edge $(v, i)$ will be a back edge and form a cycle if $i \neq = p$ i \ne p and vertex $i$ is already visited $(u se d [i] = 1)$ (used[i] = 1). If a cycle is detected, set $f l a g = 1$ flag = 1. If no cycle is detected, continue the search from vertex $i$ .

  for(int i = 0; i < n; i++)
    if ((i != p) && g[v][i])
      if(used[i]) flag = 1; else dfs(i,v);
}

The main part of the program. Read the input data.

scanf("%d",&n); 
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
  scanf("%d",&g[i][j]);

Count the number of visited vertices during the depth-first search in the variable $c$ . Set $f l a g = 0$ flag = 0 if there is no cycle in the graph. If a cycle is detected, $f l a g$ becomes $1$ .

c = 0;
flag = 0;

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

memset(used,0,sizeof(used));

Start the depth-first search from vertex $0$ . Since it is the root of the tree, it has no parent. Pass the value $- 1$ as the second argument to the dfs function.

dfs(0,-1);

The graph is not a tree if there is a back edge $(f l a g = 1)$ (flag = 1) or if the graph is not connected $(c \neq = n)$ (c \ne n).

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Algorithm implementation — checking the conditions 1) and 2)

Declare the adjacency matrix of the graph $g$ and the array $u se d$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

The dfs function implements depth-first search from vertex $v$ .

void dfs(int v)
{

Mark the vertex $v$ as visited.

  used[v] = 1;

Vertex $v$ is visited, increase $c$ by $1$ .

  c++;

Iterate over the vertices $i$ , that can be reached from $v$ . Moving from $v$ to $i$ is possible if:

There is an edge $(v, i)$ , that is $g [v] [i] = 1$ g[v][i] = 1;
The vertex $i$ is not visited $(u se d [i] = 0)$ (used[i] = 0)

If both conditions are true, we continue the depth-first search from vertex $i$ .

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

The main part of the program. Read the input value of $n$ .

scanf("%d", &n);

Count the number of edges in the graph in the variable $E d g es$ .

Edges = 0;

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

memset(used, 0, sizeof(used));

Read the adjacency matrix $g$ . Count the number of edges in the graph.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &g[i][j]);
  Edges += g[i][j];
}

Since the graph is undirected, edges $(u, v)$ and $(v, u)$ are considered the same. Divide the value of $E d g es$ by $2$ .

Edges /= 2;

Count the number of visited vertices during the depth-first search in variable $c$ .

c = 0;

Start the depth-first search from the vertex $1$ .

dfs(1);

The graph is a tree if the number of edges in it equals $n - 1$ n - 1, and also if it is connected $(c = n)$ (c = n).

if ((Edges == n - 1) && (c == n)) printf("YES\n");
else printf("NO\n");

Java implementation

import java.util.*;
//import java.io.*;

public class Main
{
  static int c = 0; 	
  static int m[][], used[];
  
  static void dfs(int v)
  {
    used[v] = 1; c++;
    for(int i = 0; i < m.length; i++) 
      if (m[v][i]== 1 && used[i] == 0) dfs(i);
  }
  
  public static void main(String[] args) //throws IOException
  {
    Scanner con = new Scanner(System.in);
    //Scanner con = new Scanner(new FileReader ("977.in"));
    int n = con.nextInt();
    m = new int[n][n];
    used = new int[n];
    Arrays.fill(used, 0);
    int Edges = 0;
    
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      m[i][j] = con.nextInt();
      Edges += m[i][j];
    }

    dfs(0); Edges /= 2;

    if ((Edges == n - 1) && (c == n)) 
      System.out.printf("YES"); 
    else 
      System.out.printf("NO");    
  }
}

Java

Python implementation — checking the conditions 1) and 3)

The dfs function performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is $p$ . If a cycle is detected, the $f l a g$ variable is set to $1$ .

def dfs(v, p):

Declare the global variables used by the function.

  global flag, c

If the graph is no longer a tree $(f l a g = 1)$ (flag = 1), there is no need to continue the search.

  if flag: return

Mark the vertex $v$ as visited.

  used[v] = 1

The vertex $v$ is visited, increase $c$ by $1$ .

  c += 1

  for i in range(n):
    if i != p and g[v][i]:
      if used[i]: flag = 1
      else: dfs(i, v)

The main part of the program. Read the input value of $n$ .

n = int(input())

Count the number of visited vertices during the depth-first search in the variable $c$ . Set $f l a g = 0$ flag = 0 if there is no cycle in the graph. When a cycle is detected, $f l a g$ becomes $1$ .

c = 0
flag = 0

All vertices are initially unvisited (initialize the list $u se d$ with zeroes).

used = [0] * n

Create an adjacency matrix $g$ , initially filled with zeroes.

g = [[0] * n for _ in range(n)]

Read the input adjacency matrix.

for i in range(n):
  g[i] = list(map(int, input().split()))

Start the depth-first search from vertex $0$ . Since it is the root of the tree, it has no parent. Pass the value $- 1$ as the second argument to the dfs function.

dfs(0, -1)

The graph is not a tree if there is a back edge $(f l a g = 1)$ (flag = 1) or if the graph is not connected $(c \neq = n)$ (c \ne n).

if flag or c != n:
  print("NO")
else:
  print("YES")

Python implementation — checking the conditions 1) and 2)

The dfs function implements depth-first search from vertex $v$ .

def dfs(v):
  global c

Mark the vertex $v$ as visited.

  used[v] = 1

The vertex $v$ is visited, increase $c$ by $1$ .

  c += 1

Iterate over the vertices $i$ , that can be reached from $v$ . Moving from $v$ to $i$ is possible if:

There is an edge $(v, i)$ , that is $g [v] [i] = 1$ g[v][i] = 1;
The vertex $i$ is not visited $(u se d [i] = 0)$ (used[i] = 0)

If both conditions are true, we continue the depth-first search from vertex $i$ .

  for i in range(1, n + 1):
    if g[v][i] and not used[i]: dfs(i)

The main part of the program. Read the input value of $n$ .

n = int(input())

Count the number of edges in the graph in the variable $E d g es$ .

Edges = 0

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

used = [0] * (n + 1)

Create an adjacency matrix $g$ , initially filled with zeroes.

g = [[0] * (n + 1) for _ in range(n + 1)]

Read the adjacency matrix $g$ . Count the number of edges in the graph.

for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))
  Edges += sum(g[i])

Since the graph is undirected, edges $(u, v)$ and $(v, u)$ are considered the same. Divide the value of $E d g es$ by $2$ .

Edges //= 2

Count the number of visited vertices during the depth-first search in variable $c$ .

c = 0

Start the depth-first search from the vertex $1$ .

dfs(1)

The graph is a tree if the number of edges in it equals $n - 1$ n - 1, and also if it is connected $(c = n)$ (c = n).

if Edges == n - 1 and c == n:
  print("YES")
else:
  print("NO")