VILLAGES - Villages by the River
In a far away country there is a wide river, N villages on the left and N villages on the right side of this river (denoted by 1..N on each side). There are also M small ships, each of them connecting one village from the left and one village from the right side (in both ways).
You are to organize a film festival in four of these villages: two from the left and two from the right side. Each two of these four villages must be connected by a ship (directly) if they belong to opposite sides of the river.
Help yourself to choose these four villages and first find out; in how many ways can you choose them?
In the first line there are integers N ≤ 1000 and M ≤ N2.
In the next M lines there are two integers from the interval [1, N] representing the village from the left and the village from the right side connected by this ship.
Print the required number of ways to choose villages for the festival.
Input: 3 5
(the only possibility is to choose the villages 1, 2 from the left and 2, 3 from the right side)
Represent sets as bits use bitsets in c++.
Last edit: 2016-10-18 20:28:34
Be sure to use bitmasks from cpp library which is heavily optimized. Passing solution is O(N^3).
plzz someone suggest any approach to solve disLast edit: 2013-06-11 21:15:46
I did this in O(n^3)