algorithm - Selecting Maximum Number of Choice

Question

We are given N fruits and M choices to select those fruits.M lines have some integers and the first one is K and each M lines follows K integers after the first value (ie. K) denoting the indices of fruit to be selected in that choice. I need to find out the maximal number of choices that can be selected.

Note :- There is only one fruit at a particular index.

Sample Input:-

4 3

2 1 2

2 2 3

2 3 4

Output :-

2

As we can select 1st and 3rd choice.

Which Algorithm should I use to solve this question ?

Answer 1

This is a variation of the maximum independent set

There are very well detailed algorithms for finding maximum independent set in this paper: Algorithms for Maximum independent Sets

And a parallel approach has been provided in this one:Lecture Notes on a Parallel Algorithm for Generating a Maximal Independent Set

And this is a java implementation.