UVA 10505 / Bipartite Matching

/***
 created: 2022-06-14-00.09.44
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'


vector<ll>g[2005];
ll v[2005];

ll bipartite(ll in)
{
    ll b=0,w=0;
    bool bicolr=1;

    queue<ll>q;

    q.push(in);
    v[in]=0;
    b++;

    while(q.empty()==false )
    {
        ll u=q.front();
        q.pop();

        for(auto d:g[u])
        {
            if(v[d]==v[u])
            {
                bicolr=0;
            }
            if(v[d]==-1)
            {
                v[d]=(v[u]+1)%2;
                if(v[d]==0) b++;
                else w++;
                q.push(d);
            }
        }
    }

    if(bicolr==0) return 0;
    return max(b,w);

}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll n,m,i,j,k,l;

        cin>>n;

        for(i=0;i<n+2;i++)
        {
            g[i].clear();
            v[i]=-1;
        }

        for(i=1;i<=n;i++)
        {
            cin>>m;
            for(j=1;j<=m;j++)
            {
                cin>>k;
                g[i].push_back(k);
                g[k].push_back(i);
            }
        }

        l=0;

        for(i=1;i<=n;i++)
        {
            if(v[i]==-1)
            {
                l+=bipartite(i);
            }
        }

        cout<<l<<nl;
    }


    get_lost_idiot;
}