PROBLEM LINK:
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;
}