首页 > 代码库 > UVa10608

UVa10608

FRIENDS

题意:找出最大的朋友圈

#include <stdio.h>#define N 30005int fa[N], ans[N];int find(int x){    return fa[x] == x ? x : fa[x] = find(fa[x]);}int main(int argc, char *argv[]){    int t, n, m, i, v1, v2, x, y, max;    scanf("%d", &t);    while(t--)    {        scanf("%d%d", &n, &m);        for(i = 1; i <= n; i++)        {            fa[i] = i;            ans[i] = 0;        }        for(i = 1; i <= m; i++)        {            scanf("%d%d", &v1, &v2);            x = find(v1);            y = find(v2);            if(x != y)                fa[x] = y;        }        for(i = 1; i <= n; i++)            ans[find(i)]++;        max = 0;        for(i = 1; i <= n; i++)            if(max < ans[i])                max = ans[i];        printf("%d\n", max);    }    return 0;}