朱色虫居
Pages
Home
Featured Posts
2007/03/01
10608-Friends
/*
"Friends"
Level:4.0
Date:2007/2/28
技巧:
利用Union-Find Algorithm & path compresssion作 Disjoint set.
並記錄每個node以下有多少個node(friends). <-對此題來說或許過於佔用記憶體. */ #include
#include
using namespace std;
int Find_Set(int); //回傳該node所屬的集合的代表node.
void Link(int,int); //相連兩個集合樹.
void Union(int,int); //聯集(呼叫前兩個function).
const int MAX_N = 30001;
int p[MAX_N], //儲存每個node的parent.
rank[MAX_N], //儲存每個node的高度.
number[MAX_N]; //儲存每個node以下的node數.
int main()
{
int num,n,m,node1,node2,max;
cin>>num;
while(num--)
{
max = 0;
scanf("%d %d",&n,&m);
for(int i=0; i < n; i++){ p[i]=i; rank[i]=0; number[i]=1; } while(m--) { scanf("%d %d", &node1, &node2); Union(node1,node2); } for(int i=0; i < n; i++) { max = max > number[i]? max : number[i];
}
cout << max << endl; } //while(1); } int Find_Set(int x) { //若x不是root, 便將parent指向root, 並回傳root node. if(x != p[x]) p[x] = Find_Set(p[x]); //recursive find root. return p[x]; } void Link(int x, int y) { if( x == y) //x,y屬同一個Set, 不需相連. return; //小樹串到大樹下. if(rank[x] > rank[y]){
p[y] = x;
number[x]+= number[y];
}
else{
p[x] = y;
number[y] += number[x]; //更新root以下的node數.
if(rank[x] == rank[y]) //兩棵樹一樣高時, 合成樹的高度會長高一個單位.
rank[y]++;
}
}
void Union(int x, int y)
{
Link(Find_Set(x),Find_Set(y)); //找到兩個node分屬的Set, 並將兩個set相連.
}
No comments:
Post a Comment
Newer Post
Older Post
Home
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment