COLOR_CC - Colors
Given a Bipartite graph with N nodes, you have to colour each node in a way such that no two adjacent nodes have the same colour. Each node is allowed to choose colour from a subset of colours. Print the possible number of ways.
You are given a symmetric matrix i.e. matrix[i][j] is always equal to matrix[j][i]. If matrix[i][j] == 'Y' then nodes i and j are connected by an edge matrix[i][j] == 'N' then nodes i and j are not connected.
Input
T number of test cases (T test cases follow).
N number of nodes in graph. N lines corresponding to matrix. N line follows: each line contains xi -- total colours ith node can take, followed by i colours.
Output
Print the possible number of ways to colour the graph.
Constraints
T will be less than 20
0 <= N <= 13, size of matrix will be N * N, and each element of matrix would be either 'Y' or 'N'.
Number of colours a node can take would be greater than equal to 0 and less than equal to 8. Colour number would be less than 100000.
Example
Input 1 4 NYNN YNNN NNNY NNYN 3 1 2 3 2 4 5 3 4 5 6 3 1 2 3 Output 54
hide comments
Scape:
2020-04-10 18:55:26
For those who are confused what should be the output when N=0, there is no case with N=0 Last edit: 2020-04-10 18:55:57 |
|
Aman Singhal:
2013-03-22 04:21:18
Will graph always be a connected graph ? |
|
Ehor Nechiporenko:
2013-02-19 13:58:29
YEES! My solution was accepted! |
Added by: | smit hinsu |
Date: | 2013-02-18 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 13 , Author : Shubhanshu Agarwal |