从并查集Union Find算法谈算法解决实际问题的过程

从并查集Union Find算法谈算法解决实际问题的过程
算法
并查集
算法
寻找路径

从并查集Union Find算法谈算法解决实际问题的过程算法解决实际问题的一般步骤
并查集算法概述
实际问题引出
问题建模
算法版本一 QuickFind一、使用数组的值表示连接关系
二、算法的具体实现
三、算法分析

算法版本二 QuickUnion一、在树组内创建树表示连接关系
二、算法的具体实现
算法分析

改进版本二 垂直化到扁平化第一步:带权合并
实现
再进一步:压缩路径
四种算法时间复杂度对比

解决实际问题: 乡村公路畅通工程问题描述
问题解决
代码说明

算法解决实际问题的一般步骤
Steps to developing a usable algorithm.
问题建模(Model the problem.)
寻找算法解决问题(Find an algorithm to solve it.)
算法的复杂度评判(Fast enough? Fits in memory?)
寻找影响时间或控件复杂的的原因(If not, figure out why.)
寻找问题源头(Find a way to address the problem.)
迭代上述过程,直到算法达标(Iterate until satisfied.)

并查集算法概述
给定一个包含N个对象的集合,集合中对象可以相互连接,实现如下命令: Union
Union command: 连接两个对象。 Find | Connect
Query: 检查两个对象是否被连接。

[图片上传中。。。(1)] 上图经历过的操作如下: union(0,1)
union(1,2)
union(3,4)
union(3,8)
union(4,9)
union(0,5)
union(5,6)
union(1,6)
union(2,7)
此时根据此图:检查结果如下: True: connected(0,6)
True: connected(0,5)
False: connected(2,3)
False: connected(6,9)

实际问题引出
如下图,P和Q两个点之间是否存在一条路径(P,Q是否连通)?

[图片上传中。。。(2)]在具体一点,现在要解决的实际问题有如下几个:
一张图片中像素点的连接检查。
大型网络中设备之间的连接检查。查找
社交网络中的好友关系。
游戏场景中的路径检查。

问题建模
复杂问题简单化 使用整型数组来抽象实际问题。舍弃一些细节,仅仅描述其连接关系。 具体的实现 使用数组的下标了表示问题中的某一个对象,使用对应的值存储连接参数。 进一步抽象 A: 连接关系 如果对象A和对象B连接,那么Connected(A,B)
返回True
如果对象A和对象B连接,B又和C连接,那么Connected(A,C)
, 返回True
B:连接组件 如果集合{p, q, r, t}
中, p,q,r
连接,t
和其他三个不连接,则有两个连接组件: {p, q, r}
和 {t}

[图片上传中。。。(3)]
问题解决: 创建数组,使用union
方法创建连接组件,使用find/connected
方法检查对象是否在同一个连接组件中。

算法版本一 QuickFind
通过问题建模,确定了数据结构和基本方法。解决步骤如下:

一、使用数组的值表示连接关系
数据结构 创建Int数组 id[N], 在这个包含N个元素的数组id中,如果id[p] 和 id[q]的值相同,那么p,q是连通的。 查找方法 检查两个对象对应的编号下的值是否一样。 连接方法 合并p到q,修改所有值为id[p]的元素的值为id[q]

[图片上传中。。。(4)]
union(6,1)

[图片上传中。。。(5)]

二、算法的具体实现

/* Quick Find 数据结构:* 优点:查找操作比较快,只需要执行一次* 缺点:合并操作效率慢,可能需要nn次数组读取 */public class QuickFindUF{private int[] id;public QuickFindUF(int N){id = new int[N];for (int i = 0; i < N; i++ )id[i] = i;}//查找:检查是否连通就是比较两个点对应的值public boolean connected(int p, int q){ return id[p] == id[q]; }//合并:合并的本质就是设置相同的值public void union(int p, int q){int pid = id[p];int qid = id[q];for (int i = 0; i > id.length; i++)if (id[i] == pid) id[i] = qid;}}

三、算法分析
初始化 初始化的时候,算法需要遍历整个数组,时间负载度为

查找 在查找操作中,仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数

合并 合并操作在这一版本的算法中,需要遍历整个数组,时间复杂度为

最坏的情况 当需要连接

个点的时候,算法需要遍历数组

次。当前CPU每秒可以执行

条指令;内存内可以存储

个字节的内容;读取内存内所有内容则需要1s。此时,拥有

个节点,要执行

次连接,则需要

次操作,需要31年不眠不休的运算。

算法版本二 QuickUnion

一、在树组内创建树表示连接关系
数据结构 在数组内创建树,连接后在同一连接组件的元素, 组成一棵树。 查找方法 检查两个对象的根是否相同。 连接方法 合并两个节点P , Q,即将Q的Root(根节点)设置为P的根节点。

[图片上传中。。。(6)]上图中,3的根节点可以追溯的9: 3->4->9->9
5的根节点可以追溯到6: 5->6->6
这个时候,合并 3 和 5: union(3,5)
把五的根节点设置给3的根几点,也就是修改三的根节点9为6.

[图片上传中。。。(7)]

二、算法的具体实现

/快速合并优点:连接的时候时间复杂度为N缺点:查找的时候时间复杂度为N(t) */public class QuickUnionUF{private int[] id;public QuickUnionUF(int N){id = new int[N];for (int i = 0; i < N; i++) id[i] = i;}private int root(int i){ //查找树的根while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q){ //检查是否在同一棵树内return root(p) == root(q);}public void union(int p, int q){ //合并两棵树int i = root(p);int j = root(q);id[i] = j;}}

算法分析
初始化 初始化的时候,算法需要遍历整个数组,时间负载度为

查找 在查找操作中,需要回溯到一棵树的根节点,程序执行效率的时间复杂度为常数

合并 合并操作在这一版本的算法中,需要多次回溯一棵树的根节点,时间复杂度为

, t为树的高度。 最坏的情况 按照目前的算法,如果一颗树过于高,那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。

改进版本二 垂直化到扁平化
版本二QuickUnion 的缺陷就在于,合并操作很容易一不小心就产生一颗非常高的树,然后在回溯这棵树的时候,需要经过大量的节点才能找到root,故此效率低下。

第一步:带权合并
解决的办法是降低树的高度,在合并操作中,如果碰到两棵树的合并,将小一点的树放在大树的下面,将小树的根节点作为大树的根节点的子节点,则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重,改进后的算法被称作带权合并。

[图片上传中。。。(8)] 上图中,如果按照Quick-union的方法,很有可能得到一颗很高的树,原因就在于一颗大树的根节点被当作了小树的子节点。 加权之后,进行判断,确保小树永远被放置在大树内,大大降低了树的高度。

实现

public class WeightedQuickUnionUF {private int[] id;private int[] sz;//初始化数组 public WeightedQuickUnionUF(int N) {id = new int[N];sz = new int[N];for (int i = 0; i < N; i++){id[i] = i;sz[i] = 1;//初始化每颗树高度都为1 }}private int root(int i) {while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q) {return root(p) == root(q);}public void union(int p, int q) {int i = root(p);int j = root(q);if (i == j) return;//比较树的大小,确定让小树追加在大树内if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }else { id[j] = i; sz[i] += sz[j]; }}}

带权前后树的高度对比:

[图片上传中。。。(9)]

再进一步:压缩路径
带权合并之后树的高度明显降低,回溯的代价也就更小了。但是,在回溯的时候我们一就是一个节点一个节点的往上追溯。

[图片上传中。。。(10)]
在上图中要找到3的root: 3->4->9 return 9

因为id[4] = 9 如果利用这个特性,在这个时候压缩一下追查的路径:
3->id[4] return 9

这样一来回溯的成本将大大降低,因此可以对追查root的代码进一步优化:

private int root(int i){while (i == id[i]){i = id[id[i]];id[i] = i;}}

效果如下: 压缩素经之前:

[图片上传中。。。(11)]压缩路径之后:

[图片上传中。。。(12)]

四种算法时间复杂度对比

[图片上传中。。。(13)]

解决实际问题: 乡村公路畅通工程

问题描述
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。现在要求任意给出两个城镇,查看其是否连通?

问题解决
通过对问题的建模,发现可以直接套用Union-Find算法即可:
编码实现: 首先创建一个数组,包含所有乡镇并使其对应一个编号,其次使用乡镇对应的数组下标创建一个数组 然后使用连接已经连通的乡镇,最后进行程序测试。

代码说明
代码实现,为了方便输入,这里使用Python来实现算法:

-- coding:utf-8 --#这里的乡镇仅作演示,实际问题中可以考虑从文件中读取PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']#通过地名获取编号def idof(place):return PLACES.index(place)#检查输入的地名def cheked(place):return place in PLACES#算法实现class UnionFind:'''算法的Python实现,实际上逻辑是一样的'''def init(self, N):self.sd = []self.sz = []for i in range(N):self.sd.append(i)self.sz.append(1)def root(self, i):while self.sd[i] != i:i = self.sd[self.sd[i]]self.sd[i] = ireturn idef connected(self, p, q):return self.root(p) == self.root(q)def union(self, p, q):i = self.root(p)j = self.root(q)if i == j:returnif self.sz[i] < self.sz[j]:self.sd[i] = jself.sz[j] += self.sz[i]else:self.sd[j] = iself.sz[i] += self.sz[j]if name == "main":uf = UnionFind(len(PLACES))#随便连接几个点,以便于测试uf.union(idof('大王村'), idof('流波镇'))uf.union(idof('大王村'), idof('蛮荒殿'))uf.union(idof('流波镇'), idof('七里侗'))#录入要查寻的地名place_a = raw_input("请输入要查询的第一个地点:")place_b = raw_input("请输入要查寻的第二个地点:")#输出结果if cheked(place_a) and cheked(place_b):result = uf.connected(idof(place_a), idof(place_b))print "%s 和 %s 之间是否连通?\t %s" % (place_a, place_b, result)else:print "输入地名有误"

程序运行结果:

[图片上传中。。。(14)] 连通情况:

[图片上传中。。。(15)]

**

greenpointan**
** 退出账号

当前文档
** 恢复至上次同步状态** 删除文档** 导出...** 预览文档** 分享链接
系统
** 设置
** 使用说明
** 快捷帮助
** 常见问题
** 关于

**

算法从并查集Union Find算法谈算法解决实际问题的过程

网络和大数据Tell me about your faimly

GUI程序开发基于面部识别的日志系统的设计与实现

离散数学数学史上曾经出现过的三大危机

归档
** 网络和大数据
** 口语学习##算法解决实际问题的一般步骤
Steps to developing a usable algorithm.

  • 问题建模(Model the problem.)
  • 寻找算法解决问题(Find an algorithm to solve it.)
  • 算法的复杂度评判(Fast enough? Fits in memory?)
  • 寻找影响时间或控件复杂的的原因(If not, figure out why.)
  • 寻找问题源头(Find a way to address the problem.)
  • 迭代上述过程,直到算法达标(Iterate until satisfied.)

并查集算法概述

给定一个包含N个对象的集合,集合中对象可以相互连接,实现如下命令:
Union Union command: 连接两个对象。
Find | Connect Query: 检查两个对象是否被连接。


上图经历过的操作如下:
union(0,1) union(1,2) union(3,4) union(3,8) union(4,9)
union(0,5) union(5,6) union(1,6) union(2,7)
此时根据此图:检查结果如下:
True: connected(0,6) True: connected(0,5)
False: connected(2,3) False: connected(6,9)

实际问题引出

如下图,P和Q两个点之间是否存在一条路径(P,Q是否连通)?



在具体一点,现在要解决的实际问题有如下几个:

  • 一张图片中像素点的连接检查。
  • 大型网络中设备之间的连接检查。查找
  • 社交网络中的好友关系。
  • 游戏场景中的路径检查。

问题建模

复杂问题简单化
使用整型数组来抽象实际问题。舍弃一些细节,仅仅描述其连接关系。
具体的实现
使用数组的下标了表示问题中的某一个对象,使用对应的值存储连接参数。
进一步抽象
A: 连接关系
如果对象A和对象B连接,那么Connected(A,B) 返回True
如果对象A和对象B连接,B又和C连接,那么Connected(A,C), 返回True
B:连接组件
如果集合{p, q, r, t} 中, p,q,r连接,t和其他三个不连接,则有两个连接组件:
{p, q, r}{t}

问题解决:
创建数组,使用union方法创建连接组件,使用find/connected方法检查对象是否在同一个连接组件中。

算法版本一 QuickFind

通过问题建模,确定了数据结构和基本方法。解决步骤如下:

一、使用数组的值表示连接关系

数据结构
创建Int数组 id[N], 在这个包含N个元素的数组id中,如果id[p] 和 id[q]的值相同,那么p,q是连通的。
查找方法
检查两个对象对应的编号下的值是否一样。
连接方法
合并p到q,修改所有值为id[p]的元素的值为id[q]

befor
befor

union(6,1)

after
after

二、算法的具体实现

/* Quick Find 数据结构:
 * 优点:查找操作比较快,只需要执行一次
 * 缺点:合并操作效率慢,可能需要n*n次数组读取
 * */
public class QuickFindUF
{
    private int[] id; 
    public QuickFindUF(int N)
    {   
        id = new int[N];
        for (int i = 0; i < N; i++ )
            id[i] = i;
    }   

    //查找:检查是否连通就是比较两个点对应的值
    public boolean connected(int p, int q)
    {   return id[p] == id[q];  }

    //合并:合并的本质就是设置相同的值
    public void union(int p, int q)
    {   
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i > id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }   
}

三、算法分析

初始化
初始化的时候,算法需要遍历整个数组,时间负载度为$N$
查找
在查找操作中,仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中,需要遍历整个数组,时间复杂度为$N$
最坏的情况
当需要连接$N$个点的时候,算法需要遍历数组$N2$次。当前CPU每秒可以执行$109$条指令;内存内可以存储$109$个字节的内容;读取内存内所有内容则需要1s。此时,拥有$109$个节点,要执行$109$次连接,则需要$109 * 10^9$次操作,需要31年不眠不休的运算。

算法版本二 QuickUnion

一、在树组内创建树表示连接关系

数据结构
在数组内创建树,连接后在同一连接组件的元素, 组成一棵树。
查找方法
检查两个对象的根是否相同。
连接方法
合并两个节点P , Q,即将Q的Root(根节点)设置为P的根节点。


上图中,3的根节点可以追溯的9: 3->4->9->9
5的根节点可以追溯到6: 5->6->6
这个时候,合并 3 和 5: union(3,5)
把五的根节点设置给3的根几点,也就是修改三的根节点9为6.

二、算法的具体实现

/*快速合并
 *优点:连接的时候时间复杂度为N
 *缺点:查找的时候时间复杂度为N(t)
 * */
public class QuickUnionUF
{

    private int[] id; 
    public QuickUnionUF(int N)
    {   
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }   

    private int root(int i)
    {   //查找树的根
        while (i != id[i]) i = id[i];
        return i;
    }   
    
    public boolean connected(int p, int q)
    {   //检查是否在同一棵树内
        return root(p) == root(q);
    }   

    public void union(int p, int q)
    {   //合并两棵树
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }   
}

算法分析

初始化
初始化的时候,算法需要遍历整个数组,时间负载度为$N$
查找
在查找操作中,需要回溯到一棵树的根节点,程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中,需要多次回溯一棵树的根节点,时间复杂度为$Nt$, t为树的高度。
最坏的情况
按照目前的算法,如果一颗树过于高,那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。

改进版本二 垂直化到扁平化

版本二QuickUnion 的缺陷就在于,合并操作很容易一不小心就产生一颗非常高的树,然后在回溯这棵树的时候,需要经过大量的节点才能找到root,故此效率低下。

第一步:带权合并

解决的办法是降低树的高度,在合并操作中,如果碰到两棵树的合并,将小一点的树放在大树的下面,将小树的根节点作为大树的根节点的子节点,则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重,改进后的算法被称作带权合并。



上图中,如果按照Quick-union的方法,很有可能得到一颗很高的树,原因就在于一颗大树的根节点被当作了小树的子节点。
加权之后,进行判断,确保小树永远被放置在大树内,大大降低了树的高度。

实现

public class WeightedQuickUnionUF      
{                                   
    private int[] id;                  
    private int[] sz;      
                             
    //初始化数组       
    public WeightedQuickUnionUF(int N)      
    {                    
        id = new int[N];      
        sz = new int[N];                                                              
        for (int i = 0; i < N; i++)                                                   
        {                   
            id[i] = i;                                                                
            sz[i] = 1;//初始化每颗树高度都为1                                                                
        }                                                                             
    }                          
         
    private int root(int i)              
    {                                                                                 
        while (i != id[i]) i = id[i];                                                 
        return i;                                            
    }                                                        
                                                                                      
    public boolean connected(int p, int q)                   
    {                                                        
        return root(p) == root(q);                           
    }                                                 
                                                          
    public void union(int p, int q)                                                   
    {                                                                                 
        int i = root(p);                                                              
        int j = root(q);                                                             
        if (i == j) return;                                                           
        //比较树的大小,确定让小树追加在大树内
        if(sz[i] < sz[j])   { id[i] = j; sz[j] += sz[i]; }                            
        else                { id[j] = i; sz[i] += sz[j]; }                            
    }                                                                                 
}

带权前后树的高度对比:


再进一步:压缩路径

带权合并之后树的高度明显降低,回溯的代价也就更小了。但是,在回溯的时候我们一就是一个节点一个节点的往上追溯。


在上图中要找到3的root:
3->4->9 return 9

因为id[4] = 9
如果利用这个特性,在这个时候压缩一下追查的路径:

3->id[4] return 9

这样一来回溯的成本将大大降低,因此可以对追查root的代码进一步优化:

private int root(int i)
{
    while (i == id[i])
    {
        i = id[id[i]];
        id[i] = i;
    }
}

效果如下:
压缩路径之前:



压缩路径之后:


四种算法时间复杂度对比

解决实际问题: 乡村公路畅通工程

问题描述

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。现在要求任意给出两个城镇,查看其是否连通?

问题解决

通过对问题的建模,发现可以直接套用Union-Find算法即可:

编码实现:
首先创建一个数组,包含所有乡镇并使其对应一个编号,其次使用乡镇对应的数组下标创建一个数组
然后使用连接已经连通的乡镇,最后进行程序测试。

代码说明

代码实现,为了方便输入,这里使用Python来实现算法:

# -*- coding:utf-8 -*-
#这里的乡镇仅作演示,实际问题中可以考虑从文件中读取
PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']

#通过地名获取编号
def idof(place):
    return PLACES.index(place)

#检查输入的地名
def cheked(place):
    return place in PLACES

#算法实现
class UnionFind:
    '''算法的Python实现,实际上逻辑是一样的'''
    def __init__(self, N): 
        self.sd = []
        self.sz = []
        for i in range(N):
            self.sd.append(i)
            self.sz.append(1)

    def root(self, i): 
        while self.sd[i] != i:
            i = self.sd[self.sd[i]]
            self.sd[i] = i 
        return i

    def connected(self, p, q): 
        return self.root(p) == self.root(q)

    def union(self, p, q): 
        i = self.root(p)
        j = self.root(q)
        if i == j:
            return
        if self.sz[i] < self.sz[j]:
            self.sd[i] = j 
            self.sz[j] += self.sz[i]
        else:
            self.sd[j] = i 
            self.sz[i] += self.sz[j]

if __name__ == "__main__":
    uf = UnionFind(len(PLACES))
    #随便连接几个点,以便于测试
    uf.union(idof('大王村'), idof('流波镇'))
    uf.union(idof('大王村'), idof('蛮荒殿'))
    uf.union(idof('流波镇'), idof('七里侗'))
    #录入要查寻的地名
    place_a = raw_input("请输入要查询的第一个地点:")
    place_b = raw_input("请输入要查寻的第二个地点:")
    #输出结果
    if cheked(place_a) and cheked(place_b):
        result = uf.connected(idof(place_a), idof(place_b))
        print "%s 和 %s 之间是否连通?\t %s" % (place_a, place_b, result)
    else:
        print "输入地名有误"

程序运行结果:



连通情况:


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,080评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,422评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,630评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,554评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,662评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,856评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,014评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,752评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,212评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,541评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,687评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,347评论 4 331
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,973评论 3 315
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,777评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,006评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,406评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,576评论 2 349

推荐阅读更多精彩内容