Breaking Into Atoms (Codechef Practice Problem)

ATOMS.cpp

/*
 *	*WARNING*
 *	If you are not familiar with bit manipulations and bitwise programming
 *	go study them first.
 *
 **************************************************************************
 *
 *  This is the solution to the practice problem 'Breaking into Atoms'
 *  on Codechef. Link to problem : http://www.codechef.com/problems/ATOMS
 *
 *  To solve this problem, for each number in set S we need to figure out 
 *  which subsets the number belongs to. If there are two numbers a and b in set S
 *  such that "if a belongs to SubSet_i then b belongs to SubSet_i too" , then
 *  essentially both a and b must belong to the same atom.
 *
 *  Notice that, the number of subsets given can be 30 at maximum (as given).
 *  This means, any number in set S can be a member of maximum 30 subsets.
 *  Now we can use 30bits to keep track of subsets which any given number belongs to.
 *  
 */

#include <iostream>
#include <algorithm>
using namespace std;

int table[100];     // 100 32bit integers. We will use these integers as bitfields
                    // to keep track of subsets.

int main(){
    int T, N, M, V, tmp, bitMask;
    cin >> T;

    while(T--){
        cin >> N >> M;
        for(int i=0; i<N; ++i) table[i] = 0x0;  // set all values in table to 0.

        for(int i=0; i<M; ++i){
            bitMask = 0x1 << i;             // This is the bitmask to set i-th bit of a 32bit int.
                                            // if a number 'n' belongs to subset i,
                                            // we will set the i-th bit of table[n] to 1.
                                            // initially all bits of table[n] are set to 0.
            cin >> V;
            while(V--){
                cin >> tmp;
                table[tmp] |= bitMask;      // here we are using the bitmask as described above.
            }
        }

        // Now we have the data about which number belongs to which subsets.
        // So, if two numbers belong to the same subsets then their corresponding entries in table
        // must be the same number. (Think why)

        // So, now the problem is reduced to finding the number of distinct entries in the array table.
        // To do this, first we SORT the array.
        sort( table, table+N );

        // And now we count the number of distinct entries.
        tmp = 1;                    // By the way, tmp is reused as the counter of distinct entries.
        for(int i=1; i<N; ++i) if(table[i] != table[i-1]) ++tmp; 

        cout << tmp << endl;        // Voila !!! Problemo Solved. 
                                    // No BIG things like sets, trees, 100x30 2D arrays needed at all. :D
    }
    return 0;
}