如何开通网上商城/郑州网站建设推广优化

等价类是满足自反性，传递性的一组关系，其具有find和union两个方法。这之前我们已经说过了。
这里我们介绍的离线等价类是find的升级版本，find只找寻root，而离线等价寻找，一个等价类的所有元素。
其原理就是首先随便寻找一个等价类元素，然后利用传递性去把所有和他相关的元素找出来。

int main()
{int n,//元素个数r;//关系个数cout<<"Enter number of elements"<<endl;cin>>n;if(n<2){cout<<"Too few elements"<<endl;return 1;}cout<<"Enter number of relations"<<endl;cin>>r;if(r<1){cout<<"Too few relations"<<endl;return 1;}arrayList<int>* list=new arrayStack<int>[n+1];//这是个数组，数组的每个元素都是一个栈//输入r个关系存储到表中int a,b;//a,b是一个关系对for(int i=1;i<r;i++){cout<<"Enter next relation/pair"<<endl;cin>>a>>b;list[a].push(b);list[b].push(a);}arrayStack<int>unprocessedList;//用来存储种子。bool *out=new bool[n+1];//用来判断元素i是否被输出for(int i=1;i<=n;i++)out[i]=false;//输出等价类for(int i=1;i<=n;i++)if(!out[i])//如果i没有被输出，则启动一个新类。{cout<<"Next class is:"<<i<<" ";out[i]=true;unprocessedList.push(i);while(!unprocessedList.empty())//开始处理{int j=unprocessedList.top();unprocessedList.pop();while(!list[j].empty()){int q=list[j].top();list[j].pop();if(!out[q])//如果元素q之前没有被输出{cout<<q<<" ";out[q]=true;unprocessedList.push[q]//将与种子关联的元素推入未处理的栈中等待处理。}}}cout<<endl;}cout<<"End of list of equivalent calsses"<<endl;return 0;
}

内部的第一个while循环完成后将输出一个等价类。下面进行一些实例讲解
假如n=9,r=11.且11个关系对为（1，5）（1，6）（3，7）（4，8）（5，2）（6，5）（4，9）（9，7），（7，8）（3，4）（6，2）
则：
list[1]=[5,6]
list[2]=[5,6]
list[3]=[7,4]
list[4]=[8,9,3]
list[5]=[1,2,6]
list[6]=[1,2,5]
list[7]=[3,9,8]
list[8]=[4,7]
list[9]=[4,7]
首先i=1;将1推入栈中且设置为输出然后
将5，6推入栈中且删除list[1]且将5，6设置为输出然后检查list[5]将1，2，6压入栈中并设置为输出，然后检查list[1]为空跳过，然后检查2发现[5,6]但是五六已经输出所以不再压入栈中。继续检查找出所有的相关元素。
将找到的元素全部设为输出之后不再处理，没找到的压入栈，并设置为true以后不再进行处理。