# Servicing Stations

Servicing Stations

A company offers personal computers for sale in N towns ( 3<=N<=35), denoted by 1, 2,..., N. There are direct routes connecting M pairs among these towns. The company decides to build servicing stations to ensure that for any town X, there will be a station located either in X or in some immediately neighboring town of X. Write a program to find the minimum number of stations the company has to build.

The input consists of multiple problem descriptions. Every description starts with number of towns N and number of town-pairs M, separated by a space. Each of the next M lines contains a pair of integers representing connected towns, at one pair per line with each pair separated by a space. The input ends with N = 0 and M = 0.

For each input case, print a line reporting the minimum number of servicing stations needed.

``````8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

``````

``````2

``````

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector < long long unsigned > edge;
bool finish;
int minimum;
long long unsigned end_tag;
long long unsigned origin_tag;

void check(int flag[], int position)
{
long long unsigned tag = origin_tag, origin = tag;
int index = 0;
for (int i = 0; i < edge.size(); i++)
{
if ((index < position) && (flag[index] == i))
{
tag |= edge[i];
if (tag > origin)
origin = tag;
else
return;
index++;
}
}

if (tag == end_tag)
{
finish = true;
minimum = index;
}
}

void generate(int flag[], int position, int positions)
{
if (finish)
return;

if (position < positions)
{
if (position == 0)
{
for (int i = 0; i < edge.size(); i++)
{
flag[position] = i;
generate(flag, position + 1, positions);
}
}
else
{
for (int i = flag[position - 1] + 1; i < edge.size(); i++)
{
flag[position] = i;
generate(flag, position + 1, positions);
}
}
}
else
check(flag, position);
}

void backtrack()
{
finish = false;

for (int i = 1; i <= edge.size(); i++)
{
int * flag = new int[edge.size()];
generate(flag, 0, i);
delete [] flag;

if(finish)
return;
}
}

bool cmp(long long unsigned x, long long unsigned y)
{
return x > y;
}

int main(int ac, char *av[])
{
int n;
int m;
int x, y;
vector < vector < int > > tmp;

while (cin >> n >> m, n && m)
{
tmp.clear();
tmp.resize(n);

for (int i = 0; i < m; i++)
{
cin >> x >> y;
if (x != y)
{
tmp[x - 1].push_back(y);
tmp[y - 1].push_back(x);
}
}

int base = 0;
origin_tag = 0;
end_tag = 0;

vector < bool > tag;
tag.resize(n);
fill(tag.begin(), tag.end(), false);

for (int i = 0; i < tmp.size(); i++)
{
if (tmp[i].size() == 0)
{
base++;
origin_tag |= ((long long unsigned)1 << i);
}

if (tmp[i].size() == 1 && tag[i] == false)
{
tag[i] = true;
if (tag[tmp[i][0] - 1] == false)
{
base++;
tag[tmp[i][0] - 1] = true;
}
}

end_tag |= ((long long unsigned)1 << i);
}

edge.clear();
for (int i = 0; i < tmp.size(); i++)
{
if (tag[i] == true)
{
origin_tag |= ((long long unsigned)1 << i);
for (int j = 0; j < tmp[i].size(); j++)
origin_tag |= ((long long unsigned)1 << (tmp[i][j] - 1));

}

if (tag[i] == false && tmp[i].size() > 0)
{
long long unsigned t = ((long long unsigned)1 << i);
for (int j = 0; j < tmp[i].size(); j++)
t |= ((long long unsigned)1 << (tmp[i][j] - 1));
edge.push_back(t);
}
}

sort(edge.begin(), edge.end(), cmp);

minimum = 0;
backtrack();

cout << base + minimum << endl;
}

return 0;
}``````

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector < long long unsigned > edge;
bool finish;
int minimum;
long long unsigned end_tag;
long long unsigned origin_tag;

void check(int flag[], int position)
{
long long unsigned tag = origin_tag, origin = tag;
int index = 0;
for (int i = 0; i < edge.size(); i++)
{
if ((index < position) && (flag[index] == i))
{
tag |= edge[i];
if (tag > origin)
origin = tag;
else
return;
index++;
}
}

if (tag == end_tag)
{
finish = true;
minimum = index;
}
}

void generate(int flag[], int position, int positions)
{
if (finish)
return;

if (position < positions)
{
if (position == 0)
{
for (int i = 0; i < edge.size(); i++)
{
flag[position] = i;
generate(flag, position + 1, positions);
}
}
else
{
for (int i = flag[position - 1] + 1; i < edge.size(); i++)
{
flag[position] = i;
generate(flag, position + 1, positions);
}
}
}
else
check(flag, position);
}

void backtrack()
{
finish = false;

for (int i = 1; i <= edge.size(); i++)
{
int * flag = new int[edge.size()];
generate(flag, 0, i);
delete [] flag;

if(finish)
return;
}
}

bool cmp(long long unsigned x, long long unsigned y)
{
return x > y;
}

int main(int ac, char *av[])
{
int n;
int m;
int x, y;
vector < vector < int > > tmp;

while (cin >> n >> m, n && m)
{
tmp.clear();
tmp.resize(n);

for (int i = 0; i < m; i++)
{
cin >> x >> y;
if (x != y)
{
tmp[x - 1].push_back(y);
tmp[y - 1].push_back(x);
}
}

int base = 0;
origin_tag = 0;
end_tag = 0;

vector < bool > tag;
tag.resize(n);
fill(tag.begin(), tag.end(), false);

for (int i = 0; i < tmp.size(); i++)
{
if (tmp[i].size() == 0)
{
base++;
origin_tag |= ((long long unsigned)1 << i);
}

if (tmp[i].size() == 1 && tag[i] == false)
{
tag[i] = true;
if (tag[tmp[i][0] - 1] == false)
{
base++;
tag[tmp[i][0] - 1] = true;
}
}

end_tag |= ((long long unsigned)1 << i);
}

edge.clear();
for (int i = 0; i < tmp.size(); i++)
{
if (tag[i] == true)
{
origin_tag |= ((long long unsigned)1 << i);
for (int j = 0; j < tmp[i].size(); j++)
origin_tag |= ((long long unsigned)1 << (tmp[i][j] - 1));

}

if (tag[i] == false && tmp[i].size() > 0)
{
long long unsigned t = ((long long unsigned)1 << i);
for (int j = 0; j < tmp[i].size(); j++)
t |= ((long long unsigned)1 << (tmp[i][j] - 1));
edge.push_back(t);
}
}

sort(edge.begin(), edge.end(), cmp);

minimum = 0;
backtrack();

cout << base + minimum << endl;
}

return 0;
}``````