How to count how many valid colourings in a graph?

Question

I attempted this SPOJ problem.

Problem:

AMR10J - Mixing Chemicals

There are N bottles each having a different chemical. For each chemical i, you have determined C[i] which means that mixing chemicals i and C[i] causes an explosion. You have K distinct boxes. In how many ways can you divide the N chemicals into those boxes such that no two chemicals in the same box can cause an explosion together?

INPUT

The first line of input is the number of test cases T. T test cases follow each containing 2 lines. The first line of each test case contains 2 integers N and K. The second line of each test case contains N integers, the ith integer denoting the value C[i]. The chemicals are numbered from 0 to N-1.

OUTPUT

For each testcase, output the number of ways modulo 1,000,000,007.

CONSTRAINTS

T <= 50

2 <= N <= 100

2 <= K <= 1000

0 <= C[i] < N

For all i, i != C[i]

SAMPLE INPUT

3

3 3

1 2 0

4 3

1 2 0 0

3 2

1 2 0

SAMPLE OUTPUT

6

12

0

EXPLANATION In the first test case, we cannot mix any 2 chemicals. Hence, each of the 3 boxes must contain 1 chemical, which leads to 6 ways in total. In the third test case, we cannot put the 3 chemicals in the 2 boxes satisfying all the 3 conditions.

The summary of the problem, given a set of chemicals and a set of boxes, count how many possible ways to place these chemicals in boxes such that no chemicals will explode. At first I used brute force method to solve the problem, I recursively place chemicals in boxes and count valid configurations, I got TLE at my first attempt.

Later I learned that the problem can be solved with graph colouring. I can represent chemicals as vertexes and there'a an edge between chemicals if they cannot be placed each other. And the set of boxes can be used as vertex colours, all I need to do was to count how many different valid colourings of the graph. I applyed this concept to solve the problem unfortunately I got TLE again. I don't know how to improve my code, I need help.

code:

#include <bits/stdc++.h>

#define MAXN 100

using namespace std;

const int mod = (int) 1e9 + 7;

int n;
int k;

int ways;

void greedy_coloring(vector<int> adj[], int color[])
{
    int u = 0;

    for (; u < n; ++u)
        if (color[u] == -1)//found first uncolored vertex
            break;

    if (u == n)//no uncolored vertexex means all vertexes are colored
    {
        ways = (ways + 1) % mod;
        return;
    }

    bool available[k];

    memset(available, true, sizeof(available));

    for (int v : adj[u])
        if (color[v] != -1)//if the adjacent vertex colored, make its color unavailable
            available[color[v]] = false;

    for (int c = 0; c < k; ++c)
        if (available[c])
        {
            color[u] = c;

            greedy_coloring(adj, color);

            color[u] = -1;//don't forgot to reset the color
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;

    cin >> T;

    while (T--)
    {
        cin >> n >> k;

        vector<int> adj[n];

        int c[n];

        for (int i = 0; i < n; ++i)
        {
            cin >> c[i];

            adj[i].push_back(c[i]);
            adj[c[i]].push_back(i);
        }

        ways = 0;

        int color[n];

        memset(color, -1, sizeof(color));

        greedy_coloring(adj, color);

        cout << ways << "\n";
    }

    return 0;
}

Answer 1

Counting the number of colorings in a general graph is #P-hard, but this graph has some special structure, which I'll exploit in a minute after I enumerate some basic properties of counting colorings. The first observation is that, if the graph has a node with no neighbors, if we delete that node, the number of colorings decreases by a factor of k. The second observation is that, if a node has exactly one neighbor and we delete it, the number of colorings decreases by a factor of k-1. The third is that the number of colorings is equal to the product of the number of colorings for each connected component. The fourth is that we can delete all but one parallel edge.

Using these properties, it suffices to determine a formula for each connected component of the 2-core of this graph, which is a simple cycle of some length. Let P(n) and C(n) be the number of ways to color a path or cycle respectively with n nodes. We use the basic properties above to find

P(n) = k (k-1)^(n-1).

Finding a formula for C(n) I think requires the deletion contraction formula, which leads to a recurrence

C(3) = k (k-1) (k-2), i.e., three nodes of different colors;
C(n) = P(n) - C(n-1) = k (k-1)^(n-1) - C(n-1).

Multiply the above recurrence by (-1)^n.

(-1)^3 C(3) = -k (k-1) (k-2)
(-1)^n C(n) = (-1)^n k (k-1)^(n-1) - (-1)^n C(n-1)
            = (-1)^n k (k-1)^(n-1) + (-1)^(n-1) C(n-1)
(-1)^n C(n) - (-1)^(n-1) C(n-1) = (-1)^n k (k-1)^(n-1)

Let D(n) = (-1)^n C(n).

D(3) = -k (k-1) (k-2)
D(n) - D(n-1) = (-1)^n k (k-1)^(n-1)

Now we can write D(n) as a telescoping sum:

D(n) = [sum_{i=4}^n (D(n) - D(n-1))] + D(3)
D(n) = [sum_{i=4}^n (-1)^n k (k-1)^(n-1)] - k (k-1) (k-2).

Break it down as two geometric sums which then cancel nicely.

D(n) = [sum_{i=4}^n (-1)^n ((k-1) + 1) (k-1)^(n-1)] - k (k-1) (k-2)
     = sum_{i=4}^n (1-k)^n - sum_{i=4}^n (1-k)^(n-1) - k (k-1) (k-2)
     = (1-k)^n - (1-k)^3 - k (k-1) (k-2)
     = (1-k)^n - (1 - 3k + 3k^2 - k^3) - (2k - 3k^2 + k^3)
     = (1-k)^n - (1-k)
C(n) = (-1)^n (1-k)^n - (-1)^n (1-k)
     = (k-1)^n + (-1)^n (k-1).

Answer 2

Note that after removing all parallel edges, we can have at most n edges. This means that in any one connected component we can only see one cycle (and simple at that), which makes the combinatorics rather straightforward. (Cycles are only dependent on how many edges each node can spawn, which is capped at 1.)

Second example:

k = 3

       << 0 <-- 3
      /   ^
     /    ^
    1 --> 2

Since cycles are self contained, any connection to one removes the possibility of another. In the example above, we cannot make a second cycle involving node 3 by adding more nodes, and the same issue would extend to any subsequent connected nodes.

It should be enough, therefore, to perform a search, separating out connected components and marking their node count and whether they contain a cycle. Given a connected component, where c of the nodes are part of a cycle and m nodes are not, we have the following formula (David Eisenstat helped me correct my combinatoric for the count of colourings of a cycle):

if the component has a cycle:
  [(k - 1)^c + (-1)^c * (k - 1)] *
  (k - 1)^(m)

otherwise:
k * (k - 1)^(m - 1)

As David Eisenstat noted, multiply all these results for the final tally.