2-SAT 输出可行解
找可行解的方案就是：
根据第一次建的图建一个反图..然后求逆拓扑排序，建反图的原因是保持冲突的两个事件肯定会被染成不同的颜色
求逆拓扑排序的原因也是为了对图染的色不会发生冲突，输出可行解就是遍历一次逆拓扑排序时染成的颜色，输出同一组颜色的解就是其中的一组可行解。
代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#include <queue> const int maxn = ;
const int maxm = ;
struct node{
int u;
int v;
int next;
}edge1[maxm], edge2[maxm];
struct tt{
int s;
int e;
int l;
}tim[maxn];
int n, m, cnt1, cnt2, scc_cnt, dfs_clock;
int head1[maxn], head2[maxn], in[maxn], ct[maxn], ans[maxn];
int sccno[maxn], dfn[maxn], low[maxn], color[maxn];
std::stack<int>st; void init(){
cnt1 = ;
cnt2 = ;
scc_cnt = ;
dfs_clock = ;
memset(in, , sizeof(in));
memset(ans, , sizeof(ans));
memset(color, , sizeof(color));
memset(sccno, , sizeof(sccno));
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(head1, -, sizeof(head1));
memset(head2, -, sizeof(head2));
} void add(int u, int v, struct node edge[], int head[], int &cnt){
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
} void dfs(int u){
low[u] = dfn[u] = ++dfs_clock;
st.push(u);
for(int i = head1[u]; i != -; i = edge1[i].next){
int v = edge1[i].v;
if(!dfn[v]){
dfs(v);
low[u] = std::min(low[u], low[v]);
}
else if(!sccno[v]){
low[u] = std::min(low[u], dfn[v]);
}
}
if(low[u]==dfn[u]){
++scc_cnt;
while(){
int x = st.top();
st.pop();
sccno[x] = scc_cnt;
if(x==u) break;
}
}
} void toposort(){
std::queue<int>qu;
for(int i = ; i <= scc_cnt; i++){
if(in[i]==) qu.push(i);
}
while(!qu.empty()){
int u = qu.front();
qu.pop();
if(color[u]==){
color[u] = ;
color[ct[u]] = -;
}
for(int i = head2[u]; i != -; i = edge2[i].next){
int v = edge2[i].v;
--in[v];
if(in[v]==) qu.push(v);
}
}
} int main(){
while(~scanf("%d", &n)){
init();
for(int i = ; i < n; i++){
int s1, s2, t1, t2, l;
int sb = scanf("%d:%d %d:%d %d", &s1, &s2, &t1, &t2, &l);
sb++;
tim[i].s = s1*+s2;
tim[i].e = t1*+t2;
tim[i].l = l;
}
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(i!=j){
if(tim[i].s<tim[j].s+tim[j].l && tim[j].s<tim[i].s+tim[i].l) add(i<<, j<<|, edge1, head1, cnt1);
if(tim[i].s<tim[j].e && tim[j].e-tim[j].l<tim[i].s+tim[i].l) add(i<<, j<<, edge1, head1, cnt1);
if(tim[i].e-tim[i].l<tim[j].s+tim[j].l && tim[j].s<tim[i].e) add(i<<|, j<<|, edge1, head1, cnt1);
if(tim[i].e-tim[i].l<tim[j].e && tim[j].e-tim[j].l<tim[i].e) add(i<<|, j<<, edge1, head1, cnt1);
}
}
}
for(int i = ; i < n+n; i++){
if(!dfn[i]) dfs(i);
}
for(int i = ; i < n+n; i++){
for(int j = head1[i]; j != -; j = edge1[j].next){
int v = edge1[j].v;
if(sccno[i] != sccno[v]){
add(sccno[v], sccno[i], edge2, head2, cnt2);
in[sccno[i]]++;
}
}
}
bool flag = false;
for(int i = ; i < n; i++){
if(sccno[i<<]==sccno[i<<|]){
flag = true;
break;
}
ct[sccno[i<<]] = sccno[i<<|];
ct[sccno[i<<|]] = sccno[i<<];
} if(flag) puts("NO");
else{
toposort();
for(int i = ; i < n+n; i++){
if(color[sccno[i]]==) ans[i] = ;
}
puts("YES");
for(int i = ; i < n; i++) {
if(ans[i<<]) printf("%02d:%02d %02d:%02d\n", tim[i].s/, tim[i].s%, (tim[i].s+tim[i].l)/, (tim[i].s+tim[i].l)%);
else printf("%02d:%02d %02d:%02d\n", (tim[i].e-tim[i].l)/, (tim[i].e-tim[i].l)%, tim[i].e/, tim[i].e%);
}
}
}
return ;
}