UVa 10608 - Friends

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

// maximum nodes in a connected subgraph

vector<int>adj[30007];
int vis[30007];
int cnt;

void dfs(int u)
{
    vis[u]=1;
    cnt++;
    REP(i,SZ(adj[u]))
    {
        if(vis[adj[u][i]]==0) dfs(adj[u][i]);
    }
}

int main()
{
    int T, n, m, u, v;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        FOR(i,1,m)
        {
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int mx=0;
        memset(vis, 0, sizeof vis);
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                cnt=0;
                dfs(i);
                mx=max(mx, cnt);
            }
        }
        pri(mx);

       FOR(i,1,n) adj[i].clear();
    }
    return 0;
}



// disjoint sets solution .. gotta take care of the pair counting -_-

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int par[30000];

void init(int node)
{
    REP(i,node) par[i] = i;
}

int find(int r)
{
    return par[r]==r ? r : par[r] = find(par[r]);
}

void make_union(int a,int b)
{
    int u=find(a), v=find(b);

    if(u != v)
        par[u]=v;
}

int main()
{
    int T,node,edge,u,v;

    cin>>T;

    while(T--)
    {
        cin>>node>>edge;

        init(node);

        REP(i,edge)
        {
            cin>>u>>v;
            make_union(u,v);
        }

        REP(i,node) find(i);

        REP(i,node) prii(i,par[i]);

        int cnt,mx = -1;

        REP(i,node)
        {
            cnt = 1;   //*********
            FOR(j,i+1,node-1)
            {
                if(par[i] == par[j]) cnt++;      //*********
            }
            mx = max(mx,cnt);
        }

        pri(mx);
    }
    return 0;
}