2014
03-20

# 并查集(2)-按秩合并和路径压缩

//  find 的原始实现
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}

// union()的原始实现
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}

假设有4个元素 0, 1, 2, 3

0 1 2 3

Do Union(0, 1)
1   2   3
/
0

Do Union(1, 2)
2   3
/
1
/
0

Do Union(2, 3)
3
/
2
/
1
/
0

继续用上面的例子
0 1 2 3

Do Union(0, 1)
1   2   3
/
0

Do Union(1, 2)
1    3
/  \
0    2

Do Union(2, 3)
1
/  |  \
0   2   3

假设集合{0, 1, .. 9} 的树表示如下所示：  当调用 find(3)时

9
/    |    \
4     5      6
/     \        /  \
0        3     7    8
/  \
1    2

9
/    /  \    \
4    5    6     3
/           /  \   /  \
0           7    8  1   2

// 用并查集判断是否存在环
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 图中的边
struct Edge
{
int src, dest;
};

// 图结构体
struct Graph
{
// V-> 顶点个数, E-> 边的个数
int V, E;

// 每个图就是 边的集合
struct Edge* edge;
};

struct subset
{
int parent;
int rank;
};

// 创建一个图
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;

graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

return graph;
}

// 使用路径压缩
int find(struct subset subsets[], int i)
{
// 找到 root并使  root 作为 i 的父节点
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// 使用按秩合并
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// 将深度较小的集合 合并到深度大的集合下面
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else //深度一样，任选一个，并增加另一个
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

int isCycle( struct Graph* graph )
{
int V = graph->V;
int E = graph->E;

struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );

for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}

for(int e = 0; e < E; ++e)
{
int x = find(subsets, graph->edge[e].src);
int y = find(subsets, graph->edge[e].dest);

if (x == y)
return 1;

Union(subsets, x, y);
}
return 0;
}

// Driver program to test above functions
int main()
{
/* 构造以下的图
0
|  \
|    \
1-----2 */

int V = 3, E = 3;
struct Graph* graph = createGraph(V, E);

graph->edge[0].src = 0;
graph->edge[0].dest = 1;

graph->edge[1].src = 1;
graph->edge[1].dest = 2;

graph->edge[2].src = 0;
graph->edge[2].dest = 2;

if (isCycle(graph))
printf( "Graph contains cycle" );
else
printf( "Graph doesn't contain cycle" );

return 0;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

4. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}