32269번 - Sphinx's Riddle 서브태스크점수다국어언어 제한함수 구현

문제

The Great Sphinx has a riddle for you. You are given a graph on $N$ vertices. The vertices are numbered from 0ドル$ to $N - 1$. There are $M$ edges in the graph, numbered from 0ドル$ to $M - 1$. Each edge connects a pair of distinct vertices and is bidirectional. Specifically, for each $j$ from 0ドル$ to $M - 1$ (inclusive) edge $j$ connects vertices $X[j]$ and $Y [j]$. There is at most one edge connecting any pair of vertices. Two vertices are called adjacent if they are connected by an edge.

A sequence of vertices $v_0 , v_1 , \dots , v_k$ (for $k ≥ 0$) is called a path if each two consecutive vertices $v_l$ and $v_{l+1}$ (for each $l$ such that 0ドル ≤ l < k$) are adjacent. We say that a path $v_0 , v_1 , \dots , v_k$ connects vertices $v_0$ and $v_k$. In the graph given to you, each pair of vertices is connected by some path.

There are $N + 1$ colours, numbered from 0ドル$ to $N$. Colour $N$ is special and is called the Sphinx's colour. Each vertex is assigned a colour. Specifically, vertex $i$ (0ドル ≤ i < N$) has colour $C[i]$. Multiple vertices may have the same colour, and there might be colours not assigned to any vertex. No vertex has the Sphinx's colour, that is, 0ドル ≤ C[i] < N$ (0ドル ≤ i < N$).

A path $v_0 , v_1 , \dots , v_k$ (for $k ≥ 0$) is called monochromatic if all of its vertices have the same colour, i.e. $C[v_l ] = C[v_{l+1} ]$ (for each $l$ such that 0ドル ≤ l < k$). Additionally, we say that vertices $p$ and $q$ (0ドル ≤ p < N,ドル 0ドル ≤ q < N$) are in the same monochromatic component if and only if they are connected by a monochromatic path.

You know the vertices and edges, but you do not know which colour each vertex has. You want to find out the colours of the vertices, by performing recolouring experiments.

In a recolouring experiment, you may recolour arbitrarily many vertices. Specifically, to perform a recolouring experiment you first choose an array $E$ of size $N,ドル where for each $i$ (0ドル ≤ i < N$), $E[i]$ is between $-1$ and $N$ inclusive. Then, the colour of each vertex $i$ becomes $S[i],ドル where the value of $S[i]$ is:

• $C[i],ドル that is, the original colour of $i,ドル if $E[i] = -1,ドル or
• $E[i],ドル otherwise.

Note that this means that you can use the Sphinx's colour in your recolouring.

Finally, the Great Sphinx announces the number of monochromatic components in the graph, after setting the colour of each vertex $i$ to $S[i]$ (0ドル ≤ i < N$). The new colouring is applied only for this particular recolouring experiment, so the colours of all vertices return to the original ones after the experiment finishes.

Your task is to identify the colours of the vertices in the graph by performing at most 2ドル,円 750$ recolouring experiments. You may also receive a partial score if you correctly determine for every pair of adjacent vertices, whether they have the same colour.

구현 상세

You should implement the following procedure.

std::vector<int> find_colours(int N,
 std::vector<int> X, std::vector<int> Y)

• $N$: the number of vertices in the graph.
• $X,ドル $Y$: arrays of length $M$ describing the edges.
• This procedure should return an array $G$ of length $N,ドル representing the colours of vertices in the graph.
• This procedure is called exactly once for each test case.

The above procedure can make calls to the following procedure to perform recolouring experiments:

int perform_experiment(std::vector<int> E)

• $E$: an array of length $N$ specifying how vertices should be recoloured.
• This procedure returns the number of monochromatic components after recolouring the vertices according to $E$.
• This procedure can be called at most 2ドル,円 750$ times.

The grader is not adaptive, that is, the colours of the vertices are fixed before a call to find_colours is made.

입력

출력

제한

• 2ドル ≤ N ≤ 250$
• $N - 1 ≤ M ≤ \frac{N \cdot (N-1)}{2}$
• 0ドル ≤ X[j] < Y [j] < N$ for each $j$ such that$ 0 ≤ j < M$.
• $X[j] \ne X[k]$ or $Y [j] \ne Y [k]$ for each $j$ and $k$ such that 0ドル ≤ j < k < M$.
• Each pair of vertices is connected by some path.
• 0ドル ≤ C[i] < N$ for each $i$ such that 0ドル ≤ i < N$.

서브태스크

힌트

예제

Consider the following call.

find_colours(4, [0, 1, 0, 0], [1, 2, 2, 3])

For this example, suppose that the (hidden) colours of the vertices are given by $C = [2, 0, 0, 0]$. This scenario is shown in the following figure. Colours are additionally represented by numbers on white labels attached to each vertex.

The procedure may call perform_experiment as follows.

perform_experiment([-1, -1, -1, -1])

In this call, no vertex is recoloured, as all vertices keep their original colours.

Consider vertex 1ドル$ and vertex 2ドル$. They both have colour 0ドル$ and the path 1ドル,ドル 2ドル$ is a monochromatic path. As a result, vertices 1ドル$ and 2ドル$ are in the same monochromatic component.

Consider vertex 1ドル$ and vertex 3ドル$. Even though both of them have colour 0ドル,ドル they are in different monochromatic components as there is no monochromatic path connecting them.

Overall, there are 3ドル$ monochromatic components, with vertices $\{0\},ドル $\{1, 2\},ドル and $\{3\}$. Thus, this call returns 3ドル$.

Now the procedure may call perform_experiment as follows.

perform_experiment([0, -1, -1, -1])

In this call, only vertex 0ドル$ is recoloured to colour 0ドル,ドル which results in the colouring shown in the following figure.

This call returns 1ドル,ドル as all the vertices belong to the same monochromatic component. We can now deduce that vertices 1ドル,ドル 2ドル,ドル and 3ドル$ have colour 0ドル$.

The procedure may then call perform_experiment as follows.

perform_experiment([-1, -1, -1, 2])

In this call, vertex 3ドル$ is recoloured to colour 2ドル,ドル which results in the colouring shown in the following figure.

This call returns 2ドル,ドル as there are 2ドル$ monochromatic components, with vertices $\{0, 3\}$ and $\{1, 2\}$ respectively. We can deduce that vertex 0ドル$ has colour 2ドル$.

The procedure find_colours then returns the array $[2, 0, 0, 0]$. Since $C = [2, 0, 0, 0],ドル full score is given.

Note that there are also multiple return values, for which 50ドル\%$ of the score would be given, for example $[1, 2, 2, 2]$ or $[1, 2, 2, 3]$.

샘플 그레이더

Input format:

N M
C[0] C[1] ... C[N-1]
X[0] Y[0]
X[1] Y[1]
...
X[M-1] Y[M-1]

Output format:

L Q
G[0] G[1] ... G[L-1]

Here, $L$ is the length of the array $G$ returned by find_colours, and $Q$ is the number of calls to perform_experiment.

첨부

• sphinx.zip