1、问题描述
例子：假定 n= 1 4， R= { ( 1 , 11 )， ( 7 , 11 )， ( 2 , 1 2 )， ( 1 2 , 8 )， ( 11 , 1 2 )， ( 3 , 1 3 )， ( 4 , 1 3 )， ( 1 3 , 1 4 )，( 1 4 , 9 )， ( 5 , 1 4 )， ( 6 , 1 0 ) }。我们忽略了所有形如 ( a , a )的关系，因为按照反身属性，这些关系是隐含的。同样也忽略了所有的对称关系。比如 ( 1 , 11) € R，按对称属性应有 ( 11,1) €R。其他被忽略的关系是由传递属性可以得到的属性。例如根据 ( 7 , 11) 和( 11 , 1 2 )，应有(7,12) €R。如果(a , b) €R，则元素a 和b 是等价的。等价类（ equivalence class）是指相互等价的元素的最大集合。 “最大”意味着不存在类以外的元素，与类内部的元素等价。 考察例 中的等价关系。由于元素 1 与11， 11 与1 2是等价的，因此，元素 1 , 11 , 1 2是等价的，它们应属于同一个等价类。不过，这三个元素还不能构成一个等价类，因为还有其他的元素与它们等价（如 7）。所以 { 1 , 11 , 1 2 } 不是等价元素的最大集合。集合 { 1 , 2 , 7 , 8 , 11 , 1 2 } 才是一个等价类。关系 R还定义了另外两个等价类： { 3 , 4 , 5 , 9 , 1 3 , 1 4 } 和{ 6 , 1 0 }。
定义：假定有一个具有 n 个元素的集合U= { 1， 2， …， n}，另有一个具有 r 个关系的集合 R= { (i1, j1) ,(i2 , j2 ), …, (ir , jr ) } 。关系 R是一个等价关系（ equivalence relation），当且仅当如下条件为真时成立： • 对于所有的 a，有(a, a) €R 时（即关系是反身的）。 • 当且仅当 (b, a) € R时(a, b) €R（即关系是对称的）。 • 若(a, b) €R且(b, c) €R，则有(a, c) € R（即关系是传递的）。 在给出等价关系 R时，我们通常会忽略其中的某些关系，这些关系可以利用等价关系的反身、对称和传递属性来获得。 在离线等价类（ o ffline equiralence class）问题中，已知 n 和R，确定所有的等价类。注意每个元素只能属于某一个等价类。
2、解决方法：
可以为n个元素分别建立一个链表，链表其他元素为与当前元素等价的元素。从头扫描元素，对于未输出过的元素，将其先压入一个堆栈，然后扫描对应这个元素的链表，并对这个链表中的元素重复着一过程。直到堆栈为空。
3、具体代码
// 离线等价类程序 #include <iostream> #include <stack> using namespace std; int main() { int n; // 元素个数 int 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; // 因错误而终止 } // 建立空栈组成的数组，stack[0]不用 stack<int> * list = new stack<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); } // 初始化以输出等价类 stack<int> unprocessedList; bool *out = new bool[n+1]; for(int i = 1; i <= n; i++) out[i] = false; // 输出等价类 for(int i = 1; i <=n; i++) { if(!out[i]) { // 启动一个新类 cout<<"Next class is: "<<i<<" "; out[i] = true; unprocessedList.push(i); // 从unprocessedList中取类的剩余元素 while(!unprocessedList.empty()) { int j = unprocessedList.top(); unprocessedList.pop(); // 表list[j]中的元素属于同一类 while(!list[j].empty()) { int q = list[j].top(); list[j].pop(); if(!out[q]) // 未输出 { cout<<q<<" "; out[q] = true; unprocessedList.push(q); } } } cout<<endl; } } cout<<"End of list of equivalence classes"<<endl; return 0; }4、输出实例
