AcyclicOrientation | Topcoder Archive

Problem Statement

You are given a simple undirected graph G on n vertices. The vertices are numbered 0 through n-1. You are given the int n and two int[]s u and v that contain the list of edges. More precisely, for each valid index i the graph contains an edge between the vertices u[i] and v[i].

An orientation of G is a directed graph that can be obtained from G by assigning one of the two possible directions to each edge of G. Let A(G) be the number of orientations of G that are acyclic. Compute and return the value A(G) modulo 6.

Definition

Class:: AcyclicOrientation
Method:: count
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int count(int n, int[] u, int[] v)
(be sure your method is public)

Constraints

n will be between 1 and 100, inclusive.
u will contain between 0 and 100 elements, inslusive.
u and v will contain the same number of elements.
Each element of u will be between 0 and n-1, inclusive.
Each element of v will be between 0 and n-1, inclusive.
G will not contain loops.
G will not contain repeated edges.

Examples

```
3
```
```
{0, 1, 0}
```
```
{2, 2, 1}
```
```
Returns: 0
```
The given graph G is a triangle. A triangle has 8 orientations. Out of these, 2 are directed cycles and 6 are acyclic. The return value is (6 modulo 6) = 0.
```
5
```
```
{0, 1, 2, 3}
```
```
{1, 2, 3, 4}
```
```
Returns: 4
```
The given graph G is a line. There are 16 orientations, and obviously all 16 are acyclic. The return value is (16 modulo 6) = 4.
```
4
```
```
{0, 3}
```
```
{1, 1}
```
```
Returns: 4
```

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.