I need help with this problem asked in Google Online Challenge. ↵
↵
You are given the following: ↵
- An integer value N ↵
- M pairs of distinct characters (lowercase English alphabets) ↵
A pair of characters in the given pairs holds a relation between them. The relation among the given pairs is also transitive, which means if you consider 2 pairs (u, v) and (v, w) which holds relation, then pair (u, w) also holds the relation. Also, the relation states that those pairs of characters cannot occur together in a formed string. ↵
Determine the total number of strings of length N such that any string does not contain a pair of adjacent characters holding any relation. Since this number can be large output it modulo 10^9+7. ↵
↵
**Constraints** ↵
1 <= T <= 10 (Number of test cases) ↵
1 <= N <= 10^4 ↵
0 <= M <= 325 (M is the number of pairs given) ↵
↵
**Example** ↵
Input: ↵
N = 2 ↵
M = 3 ↵
Pairs = [[a,b], [b,c], [c,d]] ↵
↵
Approach: ↵
- Since [a,b] and [b,c] hold a transitive relation, thus a relation among all pairs in [a, b, c] holds true. ↵
- Since [a, b, c] and [c, d] shares a transitive relation thus a relation among all pairs in [a, b, c, d] holds true. ↵
- So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc] ↵
- The strings that can be formed of length 2 are : ["aa", "ae", "af", .....] ↵
↵
Output: ↵
664 ↵
↵
↵
↵
↵
↵
You are given the following: ↵
- An integer value N ↵
- M pairs of distinct characters (lowercase English alphabets) ↵
A pair of characters in the given pairs holds a relation between them. The relation among the given pairs is also transitive, which means if you consider 2 pairs (u, v) and (v, w) which holds relation, then pair (u, w) also holds the relation. Also, the relation states that those pairs of characters cannot occur together in a formed string. ↵
Determine the total number of strings of length N such that any string does not contain a pair of adjacent characters holding any relation. Since this number can be large output it modulo 10^9+7. ↵
↵
**Constraints** ↵
1 <= T <= 10 (Number of test cases) ↵
1 <= N <= 10^4 ↵
0 <= M <= 325 (M is the number of pairs given) ↵
↵
**Example** ↵
Input: ↵
N = 2 ↵
M = 3 ↵
Pairs = [[a,b], [b,c], [c,d]] ↵
↵
Approach: ↵
- Since [a,b] and [b,c] hold a transitive relation, thus a relation among all pairs in [a, b, c] holds true. ↵
- Since [a, b, c] and [c, d] shares a transitive relation thus a relation among all pairs in [a, b, c, d] holds true. ↵
- So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc] ↵
- The strings that can be formed of length 2 are : ["aa", "ae", "af", .....] ↵
↵
Output: ↵
664 ↵
↵
↵
↵
↵
