『算法-ACM 竞赛-图论』2-SAT-Tarjan 连通分量+拓扑排序 O(N+M）模板

图论–2-SAT–Tarjan 连通分量+拓扑排序 O(N+M）模板

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#define MAXN 2000+10
#define MAXM 400000
#define INF 1000000
using namespace std;
vector<int> G[MAXN];
int low[MAXN], dfn[MAXN];
int dfs_clock;
int sccno[MAXN], scc_cnt;
stack<int> S;
bool Instack[MAXN];
int N, M;
void init()
{
    for(int i = 0; i < 2*N; i++) G[i].clear();
}
void getMap()
{
    int a, b, c;
    char op[10];
    while(M--)
    {
        scanf("%d%d%d%s", &a, &b, &c, op);
        if(op[0]=='A') //表示and
        {
            if(c==1) //表示上述关系为真，即AB为真
            {
                G[N+a].push_back(a);
                G[N+b].push_back(b);
            }
            else
            {
                G[a].push_back(b+N);
                G[b].push_back(a+N);
            }
        }
        else if(op[0]=='O')
        {
            if(c==1)
            {
                G[b + N].push_back(a);
                G[a + N].push_back(b);
            }
            else
            {
                G[a].push_back(a+N);
                G[b].push_back(b+N);
            }
        }
        else if(op[0]=='X')
        {
            if(c==1)
            {
                G[a].push_back(b+N);
                G[a+N].push_back(b);
                G[b+N].push_back(a);
                G[b].push_back(a+N);
            }
            else
            {
                G[a].push_back(b);
                G[b].push_back(a);
                G[a + N].push_back(b + N);
                G[b + N].push_back(a + N);
            }
        }
    }
}
void tarjan(int u, int fa)
{
    int v;
    low[u] = dfn[u] = ++dfs_clock;
    S.push(u);
    Instack[u] = true;
    for(int i = 0; i < G[u].size(); i++)
    {
        v = G[u][i];
        if(!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(Instack[v])
        low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        scc_cnt++;
        for(;;)
        {
            v = S.top(); S.pop();
            Instack[v] = false;
            sccno[v] = scc_cnt;
            if(v == u) break;
        }
    }
}
void find_cut(int l, int r)
{
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(sccno, 0, sizeof(sccno));
    memset(Instack, false, sizeof(Instack));
    dfs_clock = scc_cnt = 0;
    for(int i = l; i <= r; i++)
    if(!dfn[i]) tarjan(i, -1);
}
void solve()
{
    for(int i = 0; i < N; i++)
    {
        if(sccno[i] == sccno[i + N])
        {
            printf("NO\n");
            return ;
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d%d", &N, &M) != EOF)
    {
        init();
        getMap();
        find_cut(0, 2*N-1);
        solve();
    }
    return 0;
}