From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[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.



  • 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.


 #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;
     num_of_ways_optimal[x] = withNode;
     num_of_ways_optimal_cnt[x] = (withoutNodeCnt + withNodeCnt) % MOD;
 int main() {
   int tests;
   for(int test = 0; test < tests; test++) {
     int n;
     list<int> graph[n+1];
     int a, b;
     for(int i=0; i < n-1; i++) {
     int root = 1;
     dfs(graph, root, -1);
     cout<<num_of_ways_optimal[root]<<" "<<num_of_ways_optimal_cnt[root]<<"\n";