Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2006
The mayor of Madman City has decided that the city’s crossings need newer and better traffic lights. He has commissioned the company Light’s Inc. to remove the old and install the new traffic lights, because it is a very renowned company and one of the leading producers of traffic lights. The people in charge of this task (a mathematician and an engineer) have decided to minimize the ensuing chaos when the traffic lights are replaced, which entails that not all traffic lights can be replaced simultaneously. On the other hand they do not want to replace the traffic lights one at a time as that would take too long. So they decided that if they replaced the traffic lights at one intersection they would not replace the traffic lights at those intersections which were directly connected to the intersection where the traffic light was being replaced. Now the practical engineer was, of course, interested in the maximum number of intersections where the traffic lights could be replaced simultaneously, so he was looking for the largest set of intersections, where no two intersections in the set are connected by a road. The theoretical mathematician however was interested in the number of different sets of intersections in which no subset containing two intersections is connected by a road and it is not possible to add another road without violating the previous condition. Input The first line contains the number of cities which are to be processed. The following lines contain the descrition of the cities. A city consists of a number of intersections and of a number of roads which connect the intersections. The number of intersections i, 1 ≤ i ≤ 60 and the number of roads r, 1 ≤ r ≤ 3600 are on a line. The intersections are numbered from 0 . . . i−1. The following r lines contain the description of the roads. The description of a road consists of the two intersections it connects. No intersections will be connected directly by two different roads. Furthermore the graph representing the city’s network of roads will be connected. Output For each each city, output the number of sets of intersections, where no two intersections in the set are connected by a road and it is not possible to add another intersection to the set without violating the first condition, on the first line. Print the number of intersections in the largest set on the second line.
Sample Input 3 4 4 0 1 1 2 2 3 3 0 6 12 0 1 0 2 0 3 0 4 1 2 2 4 4 3 3 1 1 5 2 5 3 5 4 5 8 12 0 1 0 2 0 6 1 3 1 7 2 3 2 4 3 5 4 5 4 6 5 7 6 7
Sample Output 2 2 3 2 6 4
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// Indepdent Set(IS) is the set of vertices such that no two vertices are connected by an edge
// Maximum Indepedent Set is an IS with the maximum number of vertices fulfilling such condition
int V,E,nS,mxS;
vector < long long> adjacentMatrix; // graph of bit adj matrix, what is i connected to?
// i - current vertex
// used - bitmask of length V denoting which vertices is no longer available
// depth - depth of recursion, also the size of the independent set
void rec(int i, long long used, int depth) {
if (used == (1LL << V) - 1) { // all vertices are covered, Maximum Independent Set
nS++; // one more possible set
mxS = max(mxS, depth); // size of the set
}
else {
for (int j = i; j i+It V; j++)
if (!(used & (1LL i+It j))) // if vertex j is not yet covered yet
rec(j + 1, used | adjacentMatrix[j], depth + 1); // fast bit operation, set all reachable node adjacent to j
}
}
int main() {
int tc,a,b;
scanf("%d",&tc);
while(tc--){
nS = mxS = 0;
scanf("%d %d",&V,&E);
adjacentMatrix.assign(V,0);
for(int i=0;i i+It V;i++) adjacentMatrix[i] = 1LL i+It i; // self directed
for(int i=0;i i+It E;i++){
scanf("%d %d",&a,&b);
adjacentMatrix[a] |= (1LL i+It b);
adjacentMatrix[b] |= (1LL i+It a);
}
rec(0,0,0);
printf("%d\n%d\n",nS,mxS);
}
}
Input
4 4
0 1
1 2
2 3
3 0
6 12
0 1
0 2
0 3
0 4
1 2
2 4
4 3
3 1
1 5
2 5
3 5
4 5
8 12
0 1
0 2
0 6
1 3
1 7
2 3
2 4
3 5
4 5
4 6
5 7
6 7
Output
2
3
2
6
4
Demonstration
UVA Online Judge solution - 11065-A Gentlemen's Agreement - UVA Online Judge solution in C,C++,java