题目链接:http://acm.tju.edu.cn/toj/showp2469.html
感觉这个题目有点问题,算了不管他了,反正A了。
这里要注意的是求这个集合有多少种,那么就是要剔除重复数后,再数一下有多少个。
难一点的算法我也不会,是帆哥教我的,就是用map<int,bool>,只要maps.find(p)要是没有,就是一个不重复的集合ans++,或者maps.size();
这个题目的问题在于,father[i]里面存的是根节点,但是,我直接maps.find(father[i])却WA了,我改成p=Find_Set(i),find(p)就AC了,很不懂。
#include <stdio.h> #include <algorithm> #include <map> using namespace std; int father[105]; int Find_Set(int x) { if(x!=father[x]) father[x] = Find_Set(father[x]); return father[x]; } int main() { int t; scanf("%d",&t); while(t--) { map<int,bool> maps; int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) father[i] = i; int x,y; for(int i=0; i<m; i++) { scanf("%d%d",&x,&y); int fx = Find_Set(x); int fy = Find_Set(y); if(fx!=fy) { father[fy] = fx; } } int ans=0; for(int i=1; i<=n; i++) { int p = Find_Set(i); if(maps.find(p)==maps.end()) { maps[p] = true; ans ++; } } printf("%d ",ans); } return 0; }