题目这个题目是在数学中国上看到的，具体的题目描述如下：

问题示例：连通性（connectivity)
  假如已知一个整数对（pair)序列，其中每个整数代表某种类型的一个对象，而且将p-q对解释成“p与q连通”。
  假定关系“与…….”是可传递的：
如果p与q连通，同时q与r连通，则p与r连通.
我们的目的是编写一段程序，从集合(set）中过滤额外连接对；当程序输入一个对p-q，仅当程序此时已经看到的对不能通过可传递性证明p与q连通时，它才输出该对。如果前面的对表明p与q
连通，则程序应该忽略p-q，并继续输入下一个对。如：
3-4 3-4
4-9 4-9
8-0 8-0
2-3 2-3
5-6 5-6
2-9     2-3-4-9
5-9 5-9
7-3 7-3
4-8 4-8
5-6     5-6
0-2     0-8-4-3-2
6-1 6-1  

 

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
 
const int objectCount = 10;
const int lineCount = 12;
 
struct Line
{
    int left;
    int right;
public:
    Line (int l, int r) : left(l), right(r) {}
    Line () {}
};
 
void PrintObject(const vector<int> & object, const string& prompt = string(""));
 
// 快速查找算法。为了要与其他算法用一份源数据，所以在计算之前，复制一份数据
void QuickFind(const vector<int> & object, const vector<Line> & line)
{
    vector<int> aObject(object);  // a for assist
    vector<Line> aLine(line);
 
    for (int i=0; i<(int)aLine.size(); ++i) {
        if (aObject[aLine[i].left] == aObject[aLine[i].right]) continue;
 
        int temp = aObject[aLine[i].left];
        for (int j=0; j<(int)aObject.size(); ++j) {
            if (aObject[j] == temp) aObject[j] = aObject[aLine[i].right];
        }
    }
    PrintObject(aObject, "QuickFind");
}
 
// 快速合并算法
void QuickMerge(const vector<int> & object, const vector<Line> & line)
{
    vector<int> aObject(object);
    vector<Line> aLine(line);
 
    for (int i=0; i<(int)aLine.size(); ++i) {
        int j;
        int k;
 
        for (j=aObject[aLine[i].right]; j != aObject[j]; j = aObject[j]) ;
        for (k=aObject[aLine[i].left]; k != aObject[k]; k = aObject[k]) ;
 
        if (j == k) continue;
        aObject[k] = j;
    }
 
    PrintObject(aObject, string("QuickMerge"));
}
 
// 加权快速合并算法。增加一个数组记录每棵树的结点个数，每次合并的时候将较小的树连接到较大的树上，以防止树中长度路径的增长
void WeightedQuickMerge(const vector<int> & object, const vector<Line> & line)
{
    vector<int> aObject(object);
    vector<Line> aLine(line);
    vector<int> nodeCount(objectCount, 1);
 
    for (int i=0; i<(int)aLine.size(); ++i) {
        int j;
        int k;
 
        for (j=aObject[aLine[i].right]; j != aObject[j]; j = aObject[j]) ;
        for (k=aObject[aLine[i].left]; k != aObject[k]; k = aObject[k]) ;
 
        if (j == k) continue;
 
        if (nodeCount[j] < nodeCount[k]) {
            aObject[j] = k;
            nodeCount[j] += nodeCount[k];
        }
        else {
            aObject[k] = j;
            nodeCount[k] += nodeCount[j];
        }
    }
 
    PrintObject(aObject, string("WeightedQuickMerge"));
}
 
// 等分路径压缩
void SplitPathCompress(const vector<int> & object, const vector<Line> & line)
{
    vector<int> aObject(object);
    vector<Line> aLine(line);
 
    for (int i=0; i<(int)aLine.size(); ++i) {
        int j;
        int k;
 
        for (j=aObject[aLine[i].right]; j != aObject[j]; j = aObject[j]) {
            aObject[j] = aObject[aObject[j]];
        }
        for (k=aObject[aLine[i].left]; k != aObject[k]; k = aObject[k]) {
            aObject[k] = aObject[aObject[k]];
        }
    }
 
    PrintObject(aObject, string("SplitPathCompresse"));
}
 
// 打印数据
void PrintObject(const vector<int> & object, const string& prompt)
{
    cout << prompt << ": ";
    copy(object.begin(), object.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}
 
int main()
{
    // init
    vector<int> object(objectCount);
    for (int i=0; i<objectCount; ++i) {
        object[i] = i;
    }
    vector<Line> line;
    line.push_back(Line(3, 4));
    line.push_back(Line(4, 9));
    line.push_back(Line(8, 0));
    line.push_back(Line(2, 3));
    line.push_back(Line(5, 6));
    line.push_back(Line(2, 9));
    line.push_back(Line(5, 9));
    line.push_back(Line(7, 3));
    line.push_back(Line(4, 8));
    line.push_back(Line(5, 6));
    line.push_back(Line(0, 2));
    line.push_back(Line(6, 1));
 
    //
    QuickFind(object, line);
    QuickMerge(object, line);
    WeightedQuickMerge(object, line);
    SplitPathCompress(object, line);
    return 0;
}

 

1 对 “关于连通性问题（学习）”的想法；

评论被关闭。