IAPCR2F - Summer Trip - SOLUTION

IAPCR2F - Summer Trip is an easy DSU problem. If you don't know what Disjoint set union is, then you should first understand DSU then try solving this problem!

I've solved this problem using breadth first search (BFS).

There are T test cases, and each test case contains 'n', which denotes the number of students who are going for trip, and 'm'  denotes the number of relations between them.

Next line contains 'n' integers, which denotes the money for ith student, and next 'm' lines tells relationship between students.

After understanding the problem statement it is very clear that we need to form disjoint sets, and find money for each disjoint set.

This can be easily done by applying BFS to each such node, which is not yet visited. If we choose any node and apply BFS, we will visit all the nodes reachable from that node, and we can easily count money for each node, present in that disjoint set.

I think, now its easy to code for this problem. If you find any difficulty in coding part, refer to the following code:

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	int visit[1009];
	int val[1009];
	vector<int > a[1009];
	ll bfs(int x)
	{
	ll count=0;
	visit[x]=1;
	count+=val[x];
	list<int> q;
	q.push_back(x);
	while(!q.empty())
	{
	x=q.front();
	q.pop_front();
	for(int i=0;i<a[x].size();i++)
	{
	if(visit[a[x][i]]==0)
	{
	q.push_back(a[x][i]);
	visit[a[x][i]]=1;
	count+=val[a[x][i]];
	}
	}
	}
	return count;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll t;
	cin>>t;
	ll X=1;
	while(t--)
	{
	ll n,m;
	cin>>n>>m;
	ll sum=0;
	vi ans;
	memset(visit,0,sizeof(visit));
	for(int i=0;i<=1009;i++)
	a[i].clear();
	for(int i=1;i<=n;i++)
	cin>>val[i];
	for(int i=0;i<m;i++)
	{
	ll x,y;
	cin>>x>>y;
	a[x].push_back(y);
	//a[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
	if(!visit[i])
	{
	ans.push_back(bfs(i));
	sum++;
	}
	}
	sort(ans.begin(),ans.end());
	cout<<"Case "<<X++<<": "<<sum<<endl;
	for(int i=0;i<ans.size();i++)
	cout<<ans[i]<<" ";
	cout<<endl;
	ans.clear();
	}
	return 0;
	}
	/* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	*/

view raw IAPCR2F.cpp hosted with ❤ by GitHub