DINO5-Editorial (2021 HEADLINES)

PROBLEM LINK:

Practice
Contest

Author: Dharsan R
Tester: Dharsan R
Editorialist: Dharsan R

DIFFICULTY:

EASY

PREREQUISITES:

Graph, DFS, Connected Components

PROBLEM:

Given a Graph with N nodes and M edges, and an Array A which contains the value of the N nodes respectively.

Find the product of the defense power of the connected components of the graph where
defense power of each connected component is the sum of individual values of nodes.

Since the result can be large compute it modulo 10^9+7.

EXPLANATION:

The idea is to find the sum of values for each connected components.

Let us use a Boolean Array V to maintain the nodes that are visited. Initially none of the nodes are visited , therefore initialize all the values of the array V as false.

Perform a iteration i over 1 to N, if the i-th node is not visited i.e if V[i] is False, do a DFS traversal on that node and mark the nodes that you visit along the way as True in the boolean array V . Also while performing the DFS traversal sum up the values of nodes you visit. By this way, we can obtain the sums of all the Connected components .

Finally find the product of these sums and compute it modulo 10^9+7.

TIME COMPLEXITY:

O(N)

SOLUTIONS:

Setter's Solution
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
long long z=1000000007;
long long a[100005],v[100005];
vector<long> e[100005];
long long dfs(long node)
{
    v[node]=1;
    long long s=a[node];
    for(long i=0;i<e[node].size();i++)
    {
        if(v[e[node][i]]==0)
        {
            s=(s+dfs(e[node][i]))%z;
        }
    }
    return s%z;
}
void init()
{
	for(int i=0;i<100005;i++)
	{
		e[i].clear();
		a[i]=0;
		v[i]=0;
	}
	
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	long n,m,x,y;
	long long p;
	cin>>t;
	while(t--)
	{
		init();
	    cin>>n>>m;
	    for(long i=0;i<n;i++)
	        cin>>a[i];
	    for(long i=0;i<m;i++)
	    {
	        cin>>x>>y;
	        e[x-1].push_back(y-1);
	        e[y-1].push_back(x-1);
	    }
	    p=1;
	    for(long i=0;i<n;i++)
	    {
	        if(v[i]==0)
	        {
	            long long s=dfs(i);
	            s=s%z;
	            p=(p*s)%z;
	        }
	    }
	    cout<<(p%z)<<"\n";
	}
	return 0;
}

1 Like

Can you make questions public?

Yea sure but it will take two days time as the contest got over today.
However you can read the questions of the contest as of now.
Link: Contest Page | CodeChef

1 Like

Thank you!

Our problems has been moved to the practice session.

You can access them all here.

Corona - CRNA1
https://www.codechef.com/problems/CRNA1

Asteroid Attack - ASTR2
https://www.codechef.com/problems/ASTR2

Zombie Apocalypse - ZMBI3
https://www.codechef.com/problems/ZMBI3

Dinosaur Destruction - DINO5
https://www.codechef.com/problems/DINO5

Alien Invasion - ALIN7
https://www.codechef.com/problems/ALIN7

World War III - WOWR4
https://www.codechef.com/problems/WOWR4

The Rise of AI - TRAI6
https://www.codechef.com/problems/TRAI6

Time Travel - TMTR8
https://www.codechef.com/problems/TMTR8

1 Like