In graph theory, an independent set or stable set is a set of vertices in a graph such that no two of the vertices are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two.
Similarly, we can define a k-stable set as a set of vertices in a graph such that each vertex in the set has at most k adjacent vertices that are also in the set. So the 0-stable set is the original stable set.
You will be given a String[] graph, representing an undirected, acyclic, connected graph. The j-th character of the i-th element of graph will be 'Y' if vertices i and j are connected, or 'N' otherwise. Return a int[] containing exactly n elements, where n is the number of elements in graph. The i-th element should be the number of distinct i-stable sets in the graph modulo 112901989, where i is a 0-based index.
|