1263 - Equalizing Money

1263 - Equalizing Money

Topic: BFS

Concept: সব গুলা কম্পোনেন্ট এ চেক করবো সমান পরিমান টাকা আছে কিনা।

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int maxn = 10005;
	vector<int>graph[maxn];
	int visited[maxn];
	int a[maxn];
	set<int>st;
	bool bfs(int s)
	{
	ll money = 0;
	ll node = 0;
	queue<int>Q;
	Q.push(s);
	visited[s] = 1;
	node++;
	money += a[s];
	while(!Q.empty())
	{
	int u = Q.front();
	Q.pop();
	for(int i = 0; i < graph[u].size(); i++)
	{
	int v = graph[u][i];
	if(visited[v] == 0)
	{
	visited[v] = 1;
	money += a[v];
	node++;
	Q.push(v);
	}
	}
	}
	if( (money%node) == 0)
	{
	int res = money/node;
	st.insert(res);
	return true;
	}
	else return false;
	}
	int main()
	{
	int T;
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs++)
	{
	int n,m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
	graph[i].clear();
	visited[i] = 0;
	a[i] = 0;
	}
	st.clear();
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	while(m--)
	{
	int u,v;
	cin >> u >> v;
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	int test = 1;
	printf("Case %d: ",cs);
	for(int i = 1; i <= n; i++)
	{
	if(visited[i] == 0)
	{
	if(!bfs(i))
	{
	printf("No\n");
	test = 0;
	break;
	}
	}
	}
	if(test)
	{
	if(st.size() == 1)
	printf("Yes\n");
	else
	{
	printf("No\n");
	}
	}
	}
	return 0;
	}

view raw 1263 - Equalizing Money.cpp hosted with ❤ by GitHub

Share: