1009 - Back to Underworld

Problem Link

এটি Bipartite Graph এর প্রোব্লেম। শুধু Bipartite এর মধ্যে দুইটি সেট এর মধ্যে যার nodes বেশি তা count করলেই solution পাওয়া যাবে।

টেস্ট কেস ২:
3
1 2
2 3
4 2

ধরি, 1 হচ্ছে Vampire, তাহলে 2 অবশ্যই Lykan । যেহেতু 2 Lykan তো 3 Vampire।
তাই আমরা বলতে পারি 1,3,4 হচ্ছে Vampires এবং 2 Lykan। আর এদের মধ্যে Vampires এর সংখ্যা সর্বাধিক ।
(আমরা যদি 1 কে Lykan ধরে করতাম তাহলে Lykan এর সংখ্যা সর্বাধিক হইত, কোনটা সর্বাধিক হচ্ছে এটাতে আমার কোনো মাথা ব্যাথা নেই শুধু সর্বাধিক মানটা লাগবে।)

এখন আমরা একটা গ্রাফ আঁকব যেখানে 1 এর সাথে 2 connected, 2 এর সাথে 3 এবং 4। অর্থাৎ , Graph এর edge গুলা তাদের মধ্যের Rival Relation প্রকাশ করবে।  2 Lykan হলে এর adjacent node গুলা হবে Vampires ।   সুতরাং এখনে আমার কাজ হবে দুইটা- প্রথমত আমি Lykan & Vampires এর সংখ্যা count করব তারপর তাদের max value add করব। আর এই max value টাই হবে কাঙ্ক্ষিত result...

My Code:

#include<bits/stdc++.h>
using namespace std;
#define MAX 20001
#define Vampires 1
#define Lykans 2
vector<int>edge[MAX];
int visited[MAX];

int BFS(int source)
{
    int No_V = 0,No_L = 0;
    queue<int>q;
    q.push(source);
    visited[source] = Vampires;
    No_V++;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();

        for(int i = 0; i < edge[u].size(); i++)
        {
            int v = edge[u][i];
            if(visited[v]==0)
            {
                if(visited[u]==Vampires)
                {
                    visited[v] = Lykans;
                    No_L++;
                }
                else
                {
                    visited[v] = Vampires;
                    No_V++;
                }
                q.push(v);
            }
        }
    }

    return max(No_L,No_V);
}

int main()
{
    int T;
    cin>>T;
    for(int t = 1; t <= T; t++)
    {
        int n, mx = 0;
        scanf("%d",&n);
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < MAX; i++)
            edge[i].clear();

        for(int i = 0; i < n; i++)
        {
            int u, v;
            scanf("%d %d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }

        for(int i = 1; i < MAX; i++)
        {
            if(!edge[i].empty() && visited[i]==0)
            {
                mx+=BFS(i);
            }
        }

        printf("Case %d: %d\n",t,mx);
    }

    return 0;
}