Recently we were solving problems from past Indian ICPC regional . We weren't able to solve these 2 problems , and I couldn't find any editorial either . It would be really helpful if you guys can give me some hints to these problems.↵
↵
### [Chemicals](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=380&page=show_problem&problem=3118) ↵
↵
#### Description ↵
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?↵
↵
#### Constraints ↵
- $T \leq 50$↵
- $2 \leq N \leq 100$↵
- $2 \leq K \leq 1000$↵
↵
#### My Ideas↵
I thought of modelling the given dependencies as a graph and we are asked to find the number of ways to partition the graph into independent sets . But I realised that counting independent sets is intractable , so there must be a much more efficient or different way to solve this problem .
↵
### [Chemicals](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=380&page=show_problem&problem=3118) ↵
↵
#### Description ↵
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?↵
↵
#### Constraints ↵
- $T \leq 50$↵
- $2 \leq N \leq 100$↵
- $2 \leq K \leq 1000$↵
↵
#### My Ideas↵
I thought of modelling the given dependencies as a graph and we are asked to find the number of ways to partition the graph into independent sets . But I realised that counting independent sets is intractable , so there must be a much more efficient or different way to solve this problem .
