LightOJ 1263 Equalizing Money

//Unsorted Ideas:
নোড আছে এজ আছে। নোডদের কাছে বিভিন্ন পরিমানে টাকা আছে। গ্রাফের মত বিভিন্ন এজে কানেক্টেড লোক গুলা। তারা চাইলে এক আরেকজনকে টাকা দিতে পারবে সবার সমান টাকা করার জন্য । যদি তারা এজ দিয়ে কানেক্টেড থাকে।

 তার মানে সহজ কথায় এই গ্রাফে যেহেতু এক বা একাধিক ডিসজয়েন্ট গ্রুপে ভাগ হয়ে থাকবে লোকজন। তো এজ এর কানেকশানে টাকা দিতে পারবে মানে আলাদা আলাদা গ্রুপে নিজেদের মধ্যে টাকা দিতে নিতে পারবে। তো এখন যেহেতু প্রব্লেমে বলা আছে ফাইনালি সবার কাছে সমান পরিমান টাকা থাকবে সো, আমরা ধরেই নিতে পারি সবার কাছে (টোটাল টাকা / মানুষ) মানে এভারেজ যেই টাকা টা আসে মোট টাকার সেটা সবার কাছে থাকবে। 

 এখন যেহেতু ডিসজয়েন্ট সেটে আলাদা আলাদা গ্রুপে টাকা আদান প্রদান হতে পারে। এক গ্রুপের সাথে আরেক গ্রুপেরে রিলেশান নাই। কিন্তু তাদের প্রত্যেকের টাকা আলাদা ভাবে অবশ্যই এভরেজ হতে হবে। তাই আমরা চাইলে সব আলাদা গ্রুপের জন্য ওই গ্রুপের মানুষ কত, আর টাকা কত সেটা ডিএফএস অর ইউনিয়ন ফাইন্ড দিয়ে বের করতে পারি।

তখন দেখব যে বের টাকা দিয়ে মানুষ এর সংখ্যা ডিভিজিবল কিনা। যদি না হয় তাহলে সম্ভব না। 
আর যদি হয় ও , তখন দেখতে হবে ওই গ্রুপের সবার কাছে আমাদের অল ইকুয়েল করার জন্য যেই এভরেজ ভেবে রেখেছিলাম তার সাথে ম্যাচ করে কিনা। যদি না করে তাহলেও সম্ভব না। 

এইতো... রাফ আইডিয়া... এটাই... :D  :/ 

Code : 

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 10007

ll n,e,u,v;
ll mny[1234];
vector<int> adj[sz];
int ppl,tot,sm;
bool vis[1234];


void dfs(int u)
{
    tot += mny[u];
    ppl++;
    vis[u] = 1;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];
        if(vis[v]==0)
        {
            dfs(v);
        }
    }

}

int main()
{

    ll t,cs=0;
    scl(t);
    while(t--)
    {
        sm = 0;
        scll(n,e);
        REP(i,n) scl(mny[i]), sm += mny[i];

        int fl = 0;

        REP(i,e)
        {
            scll(u,v);
            u--,v--;
            adj[u].pb(v);
            adj[v].pb(u);
        }

        int avg = sm/n;     //each getting equal mny finally

        REP(i,n)
        {

            ppl = 0;
            tot = 0;
            if(vis[i]==0)
            {
                dfs(i);

                if(tot%ppl!=0)
                {
                    fl=1;
                    break;
                }
                else
                {
                    if(avg != tot/ppl)
                    {
                        fl =1;
                        break;
                    }
                }
            }

        }

        printf("Case %lld: ", ++cs);

        if(fl) puts("No");
        else puts("Yes");

        REP(i,sz) adj[i].clear();
        mem(vis,0);
    }

    return 0;
}