977. Is it a Tree?

 

An undirected graph without loops and multiple edges is given by an adjacency matrix. Determine whether this graph is a tree.

 

Input. The first line contains the number of vertices n (1 ≤ n ≤ 100) in the graph. Then, an adjacency matrix of size n × n is given, where 1 indicates the presence of an edge, and 0 indicates its absence. The matrix is symmetric with respect to the main diagonal.

 

Output. Print “YES” if the graph is a tree, and “NO” otherwise.

 

Sample input

Sample output

3

0 1 0

1 0 1

0 1 0

YES

 

 

SOLUTION

graphs – depth first search

 

Algorithm analysis

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

1.   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.

2.   |V| = |E| + 1. If the graph is a tree, then it contains n – 1 edges.

3.   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 realization – checking the conditions 1) and 3)

Declare the adjacency matrix of the graph g and the array used.

 

#define MAX 110

int m[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 flag variable is set to 1.

 

void dfs(int v, int p)

{

 

If the graph is no longer a tree (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 ip and vertex i is already visited (used[i] = 1). If a cycle is detected, set 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 flag = 0 if there is no cycle in the graph. If a cycle is detected, flag becomes 1.

 

c = 0;

flag = 0;

 

All vertices are initially unvisited (initialize the array used 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 (flag = 1) or if the graph is not connected (cn).

 

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

 

Algorithm realization – checking the conditions 1) and 2)

Declare the adjacency matrix of the graph g and the array used.

 

#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;

·        The vertex i is not visited (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 Edges.

 

Edges = 0;

 

All vertices are initially unvisited (initialize the array used 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 Edges 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, and also if it is connected (c = n).

 

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

else printf("NO\n");

 

Java realization

 

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");   

  }

}  

 

Python realization – 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 flag 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 (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

 

The edge (v, i) will be a back edge and form a cycle if ip and vertex i is already visited (used[i] = 1). If a cycle is detected, set flag = 1. If no cycle is detected, continue the search from vertex i.

 

  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 flag = 0 if there is no cycle in the graph. When a cycle is detected, flag becomes 1.

 

c = 0

flag = 0

 

All vertices are initially unvisited (initialize the list used 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 (flag = 1) or if the graph is not connected (cn).

 

if flag or c != n:

  print("NO")

else:

  print("YES")

 

Python realization – 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;

·        The vertex i is not visited (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 Edges.

 

Edges = 0

 

All vertices are initially unvisited (initialize the array used 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 Edges 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, and also if it is connected (c = n).

 

if Edges == n - 1 and c == n:

  print("YES")

else:

  print("NO")