AcyclicOrientation
SRM 717 · 2017-05-20 · by Arterm
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
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.
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.
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
3
{0, 1, 0}
{2, 2, 1}
Returns: 0
5
{0, 3, 1, 2}
{3, 1, 2, 4}
Returns: 4
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AcyclicOrientation with a public method int count(int n, vector<int> u, vector<int> v) · 56 test cases · 2 s / 256 MB per case