Family | Topcoder Archive

Problem Statement

A directed acyclic graph is a family graph if the following constraints are all satisfied:

The nodes of the graph are numbered 0 through N-1, for some positive N.
Each node is either male or female.
Each node either has no parents, or it has precisely two parents. (A parent of the node x is a node y such that there is an edge from y to x.)
If a node has parents, their numbers are strictly smaller than the number of the node.
If a node has parents, one of them must be male and the other female.

You are given two int[]s parent1 and parent2 with N elements each. These describe one directed graph that resembles a family graph: For each i, node i has either two parents (in which case parent1[i] and parent2[i] are their numbers, and both of them are smaller than i), or it has no parents (in which case parent1[i] and parent2[i] are both -1).

Return "Possible" (quotes for clarity) if the given graph can be a family graph, and "Impossible" otherwise.

Definition

Class:: Family
Method:: isFamily
Parameters:: int[], int[]
Returns:: String
Method signature:: String isFamily(int[] parent1, int[] parent2)
(be sure your method is public)

Constraints

parent1 will contain between 1 and 100 elements, inclusive.
parent1 and parent2 will contain the same number of elements.
For each i, the i-th element (0-based) of parent1 will be between -1 and i-1, inclusive.
For each i, the i-th element (0-based) of parent2 will be between -1 and i-1, inclusive.
For each i, the i-th element of parent1 will be -1 if and only if the i-th element of parent2 is -1.
For each i, if the i-th element of parent1 is not -1, then the i-th element of parent1 and the i-th element of parent2 will be different.

Examples

```
{-1,-1,0}
```
```
{-1,-1,1}
```
```
Returns: "Possible"
```
The parents of node 2 are nodes 0 and 1. Nodes 0 and 1 have no parents.

{-1,-1,-1,-1,-1}

{-1,-1,-1,-1,-1}

Returns: "Possible"

Nobody has any parents.

```
{-1,-1,0,0,1}
```
```
{-1,-1,1,2,2}
```
```
Returns: "Impossible"
```
Given that 0 and 1 have a child, their genders must be different. Given that 0 and 2 have a child, their genders must be different, too. Then, 1 and 2 must have the same gender, hence they cannot have a child together. Therefore, this cannot be a valid family graph.

{-1,-1,-1,-1,1,-1,0,5,6,-1,0,3,8,6}

{-1,-1,-1,-1,3,-1,4,6,5,-1,5,4,6,1}

Returns: "Possible"

{-1,-1,-1,2,2,-1,5,6,4,6,2,1,8,0,2,4,6,9,-1,16,-1,11}

{-1,-1,-1,1,0,-1,1,4,2,0,4,8,2,3,0,5,14,14,-1,7,-1,13}

Returns: "Impossible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.