题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1814
题意：给出一个数n,代表有n个党派,每个党派要求派出其中一个人去参加会议，且只能派出一人。给出m,m行每行给出a, b.代表处于不同党派中的a, b也具有矛盾关系,a, b其中也只能有一位去参加会议。这2 * n个人的编号为1 ~ 2 * n,其中 2 * i 与 2 * i - 1是属于同一个党派。要求找到一个编号字典序最小的方案。
思路：
1.每个集合中只有2个元素，并且给出部分元素之间的限制关系，典型的2-sat问题。
2.找到对立点，建‘矛盾边’，用tarjan缩点，再判断对立点是否处在一个强连通分量中，若处在则无解，若都不处在就有解。这种思路在这道题是不可行的，因为题目要求最小字典序输出。
3.由于要保证最小字典序，我们可以用染色法来求解。每个人的编号我们默认 -1 ，这样就可以运用 ^1 运算来处理同一帮派中的2个人。从0号开始遍历到2 * n - 1号人，这样寻找方案就是最小字典序。
4.扩展：若同一对点的编号是不连续的，例如0-5,1-9,3-4. 那么我们就要用结构体排序（结构体中2个变量分别代表同一帮派中的2个人的编号），将同一点对中小的那个点按照从小到大的顺序排序，保证遍历的时候的字典序。（加矛盾边不需要处理）
代码里的注释很详细。
#include<stdio.h>
#include<string.h>
#define mem(a, b) memset(a, b, sizeof(a)) int n, m;
int head[], cnt;
int vis[], sum, node[]; struct Edge
{
int to, next;
}edge[ * ]; void add(int a, int b)
{
edge[++ cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt;
} void init()
{
mem(head, -), cnt = ;
mem(vis, );
} int dfs(int now)
{
if(vis[now ^ ])//若帮派中另一个人已经被选择,则自己一定不会被选择,返回0
return ;
if(vis[now])//若自己已经被选择,则不用再dfs了,已经找过从自己出发的方案
return ;
node[sum ++] = now;//记录查找过程中的点是哪些
vis[now] = ;
for(int i = head[now]; i != -; i = edge[i].next)//不同帮派中的矛盾关系
{
int to = edge[i].to;
if(!dfs(to))//这些边代表'必须', 不能选b,就必须选择b ^ 1,若b ^ 1找不到合理方案,说明就不存在方案了,返回0
return ;
}
return ;
} int two_sat() //返回是否存在方案
{
for(int i = ; i < * n; i += ) //由小到大遍历, 保证在有合理的方案的情况下的字典序
{
if(!vis[i] && !vis[i ^ ]) //若遍历到有帮派中2人都未被标记, 则确定之前的标记,代表是合法方案的一部分, sum清为0
{
sum = ;
if(!dfs(i))//暴力寻找的过程中发现不存在,那么该过程中被标记的点都重新处理为未被标记
{
while(sum)
vis[node[-- sum]] = ;
if(!dfs(i ^ ))//若帮派中另一个人也找不到合理方案,那么就不存在方案了,直接retrun 0
return ;
}
}
}
return ;
} int main()
{
while(scanf("%d%d", &n, &m)!=EOF)
{
init();
for(int i = ; i <= m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
a --, b --; //形成 ^1 运算关系
add(a, b ^ ), add(b, a ^ );
}
if(two_sat())
{
for(int i = ; i < * n; i += )
{
if(vis[i])
printf("%d\n", i + );
else
printf("%d\n", (i ^ ) + );
}
}
else
printf("NIE\n");
}
return ;
}