 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
看来这个题并查集的好坏对时间并不起多大影响,刚才去了路径压缩,592毫秒In Reply To:这个并查是路径压缩么？ 怎么做路径压缩？ Posted by:sunmoonstar_love at 2005-07-28 22:06:56 > int GetRoot(int x){
> if(colorset[x] < 0) return x;
> else return GetRoot(colorset[x]);
> }
>
> void Union (int a, int b){
> int rootA = GetRoot(a);
> int rootB = GetRoot(b);
>
> if(rootA == rootB) return;
>
> if(colorset[rootA] <= colorset[rootB]){
>
> colorset[rootA] += colorset[rootB];
> colorset[rootB] = rootA;
>
> if(colorset[rootA] == -1*setsize){
> printf("Possible\n");
> exit(0);
> }
> } else {
> colorset[rootB] += colorset[rootA];
> colorset[rootA] = rootB;
>
> if(colorset[rootB] == -1*setsize){
> printf("Possible\n");
> exit(0);
> }
> }
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
