SPOJ VOCV

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

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[edit]

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[edit]

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>