首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。