SPOJ VOCV

Summary

The city of Y-O is a network of two-way streets and junctions with the following properties:

There is no more than one street between each pair of junctions. Every junction is connected to every other junction either directly via a street or through other junctions by a unique path. When a light is placed at a junction, all the streets meeting at this junction are also lit.

A valid lighting is a set of junctions such that if lights were placed at these, all the streets would be lit. An optimal lighting is a valid lighting such that it contains the least number of junctions.

The task is divided into two subtasks:

Find the number of lights in an optimal lighting. Find the total number of such optimal lightings in the city.

Explanation

Note

• the given graph is not cyclic.
• you either have to choose a vertex (or) you will definitely have to choose all the vertices connected to it.
• the optimal answer will be achieved by selecting an node or not selecting a node.

Implementations

c++
#include<iostream>
#include <list>

const int MOD = 10007;
const int MAXN = 100010;

using namespace std;

int num_of_ways_optimal[MAXN];
int num_of_ways_optimal_cnt[MAXN];
int num_of_ways_with[MAXN];
int num_of_ways_with_cnt[MAXN];

void dfs(list<int> graph[], int x, int parent) {
list<int> x_adj = graph[x];
int withNode = 1, withNodeCnt = 1, withoutNode = 0, withoutNodeCnt = 1;
for (std::list<int>::iterator y = x_adj.begin(); y != x_adj.end(); y++) {
if(*y != parent) {
dfs(graph, *y, x);
withNode += num_of_ways_optimal[*y];
withNodeCnt = (withNodeCnt * num_of_ways_optimal_cnt[*y]) % MOD;

withoutNode += num_of_ways_with[*y];
withoutNodeCnt = (withoutNodeCnt * num_of_ways_with_cnt[*y]) % MOD;
}
}

num_of_ways_with[x] = withNode;
num_of_ways_with_cnt[x] = withNodeCnt;

if(withNode < withoutNode) {
num_of_ways_optimal[x] = withNode;
num_of_ways_optimal_cnt[x] = withNodeCnt;
}
else if(withNode > withoutNode) {
num_of_ways_optimal[x] = withoutNode;
num_of_ways_optimal_cnt[x] = withoutNodeCnt;
}
else{
num_of_ways_optimal[x] = withNode;
num_of_ways_optimal_cnt[x] = (withoutNodeCnt + withNodeCnt) % MOD;
}
}

int main() {
int tests;
cin>>tests;
for(int test = 0; test < tests; test++) {
int n;
cin>>n;

list<int> graph[n+1];
int a, b;
for(int i=0; i < n-1; i++) {
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}

int root = 1;
dfs(graph, root, -1);
cout<<num_of_ways_optimal[root]<<" "<<num_of_ways_optimal_cnt[root]<<"\n";
}
}

</syntaxhighlight>