URAL 1382 Game with Cards

题解

2-SAT 一眼题，但是很遗憾，我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解，我个人以为，只要染色数量等于点数就是可行解。有哪里不对的么？？

但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。

传送门

题意
有n个人手中有n张卡，每个人说两句话，有一句必定为真，有一句必定为假。说了2-sat一眼题……
两句话分别说，我自己手上是几号卡，别人手上是几号卡，保证不存在相同的陈述。

思路：
对于每两个人 i 和 j 的陈述，进行判断，如果产生矛盾，则建边。

产生矛盾是指两个的陈述，主语或者谓语有一个不同就产生了矛盾。
eg
1 号 手中有 2 号卡 < —- > 1 号手中有 3 号卡
1 号 手中有 2 号卡 < —- > 2 号手中有 2 号卡

两人的陈述分别是

1. 暴力法
2. Tarjan
3. Kosaraju

第三种算法昨天才知道，现在还没学，先贴上 1 和 2 的AC Code

暴力法

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;

int idx, n, m, vis_time, top;
int head[maxn], st[maxn];
bool instack[maxn], vis[maxn];
int a[maxn], b[maxn], c[maxn], num[maxn];

struct node {
    int to;
    int nxt;
} edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i < 2 * n; i++)
        head[i] = -1;
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

bool dfs(int u)
{
    if (vis[u ^ 1])
        return false;
    if (vis[u])
        return true;
    vis[u] = true;
    st[top++] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt)
        if (!dfs(edges[id].to))
            return false;
    return true;
}

bool solve()
{
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            top = 0;
            if (!dfs(i)) {
                while (top)
                    vis[st[--top]] = false;
                if (!dfs(i + 1))
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    if (solve())
        for (int i = 0; i < n; i++)
            printf("%d ", vis[i << 1] ? 1 : 2);
    return 0;
}

Tarjan

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;

int idx, tpidx, n, m, scc, top, vis_time;
int head[maxn], tphead[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn], vis[maxn], judge[maxn];
int a[maxn], b[maxn], c[maxn], indegree[maxn];
int crs[maxn], col[maxn];

queue<int> que;

struct node {
    int from, to;
    int next;
} edges[1005 * 1005 * 2], tp_edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].from = u;
    edges[idx].to = v;
    edges[idx].next = head[u];
    head[u] = idx++;
}

void addTPEdge(int u, int v)
{
    tp_edges[tpidx].from = u;
    tp_edges[tpidx].to = v;
    tp_edges[tpidx].next = tphead[u];
    tphead[u] = tpidx++;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            color[v] = scc;
        } while (v != u);
    }
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

void topoSort()
{
    for (int i = 1; i <= scc; i++)
        if (indegree[i] == 0)
            que.push(i);
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        if (col[cur] == 0) {
            col[cur] = 1;
            col[crs[cur]] = -1;
        }
        for (int id = tphead[cur]; ~id; id = tp_edges[id].next)
            if (--indegree[tp_edges[id].to] == 0)
                que.push(tp_edges[id].to);
    }
}

bool getAns()
{
    for (int i = 0; i < n; i++) {
        if (color[i << 1] == color[i << 1 | 1])
            return false;
        crs[color[i << 1]] = color[i << 1 | 1];
        crs[color[i << 1 | 1]] = color[i << 1];
    }
    for (int i = 0; i < idx; i++) { 
        if (color[edges[i].from] != color[edges[i].to]) {
            addTPEdge(color[edges[i].to], color[edges[i].from]);
            indegree[color[edges[i].from]]++;
        }
    }
    topoSort();
    for (int i = 0; i < n; i++)
        judge[i] = col[color[i << 1]] == 1 ? true : false;
    return true;
}

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i < 2 * n; i++)
        tphead[i] = head[i] = -1;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    for (int i = 0; i < 2 * n; i++)
        if (dfn[i] == 0)
            tarjan(i);
    if (getAns())
        for (int i = 0; i < n; i++)
            printf("%d ", judge[i] ? 1 : 2);
    return 0;
}