Is it a Tree?

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mine is playing a game with Tatsumi, where one person sketches some branches and knots and the other determines whether the sketch is of a tree or not. After playing this for a few hours, they've gotten bored and have decided to make the game more abstract. Now, instead of drawing pictures of trees, the couple fill in a 4\cdot4 adjacency matrix with either 0 or 1.

Their adjacency matrix stores the relationship between any two knots u and v. Specifically, if adj[u][v] = 1, then there is a branch connecting u \rightarrow v. Since branches are undirected, a branch from u \rightarrow v implies a branch from v \rightarrow u. In this way, the adjacency matrix is symmetrical in that adj[u][v] = adj[v][u].

An adjacency matrix representing a tree has exactly one path between any pair of u and v, and hence has 1 less branches than it has knots. Any less and the tree would be disconnected (a forest), and any more and a cycle would exist.

You've decided to join in the fun. Given a 4\cdot4 adjacency matrix, can you determine whether it represents a tree or not?

Input Specification

An adjacency matrix, represented by 4 lines, each containing 4 space-separated integers, either 0 or 1.

Output Specification

Yes if the given adjacency matrix represents a tree, or No otherwise.


If you are unfamiliar with the definition of a tree, this Wikipedia article might help.

Sample Input 1

0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0

Sample Output 1


Sample Input 2

0 1 0 1
1 0 0 1
0 0 0 1
1 1 1 0

Sample Output 2


Explanation of Output for Sample Input 2

Between Sample 1 and Sample 2 there is a difference of one branch: 0 \longleftrightarrow 1. This branch creates a cycle, and therefore the number of knots is the same as the number of branches. Hence, it is not a tree.