數集合有多少個TOJ(2469)

題目鏈接：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\n",ans);}return 0;
}

?