11065 - A Gentlemen's Agreement

[shanto86]

well i got AC this morning. the idea given above is nothing but garbage.

actually i though that i only needed the maximum size, but later i noticed that i also need total as well...

if it was only maximum then that would come to play!

[sluga]

Could someone write here the 6 intersection sets in the last example in the sample input? I only find 2 of them, no matter what I do ( I even searched for sets using O( 2^n ) algorithm ).
Those I find are:
0 3 4 7
1 2 5 6

( edit )
I realize my mistake now... I thought the first number was the number of maximal sets.

[rammestain]

please give me hint for solving this problem

[satej]

I guess the test cases in the input aren't too tough.
I've used backtracking with some pruning to generate every independent set, and it got just ~0.6 seconds.

The maximum answer can be 2^30. So a backtracking solution should not work for such limits.

[mf]

The maximum answer can be 2^30.

So, can you please show a test case where the answer would be 2^30?
(Don't forget, that "the graph representing the city's network of roads [should] be connected.")