首页 > 代码库 > UVA 10608 Friends

UVA 10608 Friends

很水的并查集

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 30010int N,M;int p[MAXN],num[MAXN];int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}int main(){    //freopen("sample.txt","r",stdin);    int T;    scanf("%d",&T);    while (T--)    {        scanf("%d%d",&N,&M);        int ans = 0;        for (int i = 0; i <= N; i++) {p[i] = i; num[i] = 1;}        while (M--)        {            int u,v;            scanf("%d%d",&u,&v);            int x = Find(u);            int y = Find(v);            if (x != y)            {                if (num[x] > num[y])                {                    p[y] = x;                    num[x] += num[y];                }                else                {                    p[x] = y;                    num[y] += num[x];                }                ans = max(ans,max(num[x],num[y]));            }        }        printf("%d\n",ans);    }    return 0;}

 

UVA 10608 Friends