算法概论作业5.26 5.28 5.33

以下是程序自动分析中的一个问题。对于一组变量x1,x2,…,xn,给定一些形如“xi=xj”的等式约束和形如“xi≠xj”的不等式约束这些约束能否同时满足？
例如，如下一组约束：x1=x2,x2=x3,x3=x4,x1≠x4，是无法同时满足的，请给出一个有效的算法，判断关于n个变量的m个约束是否可同时满足。

1.先处理相等约束，对相等的变量进行并集操作。
2.检查不等约束，
若不等号两边的变量位于同一个集合，则说明该约束条件是不可满足的，
若所有位于不等号两边的变量都位于不同集合中，即说明该约束条件是可满足的。

Alice想要举办一个舞会，为此需要决定邀请什么人参加。目前共有n个人可供选择， Alice根据他们之间是否相识列出了一个相互配对的列表。她希望邀请尽可能多的人参加，但同时必须考虑以下两点：在舞会上，每个人至少可以各找到5个相识和5个不相识的人。
请就此问题给出一个高效的算法，以n个人的列表及其相识配对列表为输入，输出最优的被邀请客人名单。并基于变量n估算其运行时间。

1、建立无向图G(V,E)，并求出每个顶点的度
2、遍历所有顶点，若满足d(v)<5或者d(v)>6,则将顶点v放入一个待删除队列delete中
3、将待删除顶点删除，更新相关顶点的度，重复2 直至delete队列为空。

第一步，建立相识配对列表
第二步：遍历所有顶点，若满足d(v)<5或者d(v)>6,则将顶点v放入一个待删除队列delete
第三步：得出邀请名单

请说明如何实现一个关于公式长度为线性时间的Horn公式可满足性问题的吝啬算法。