luoguP6378 [PA2010]Riddle 2-SAT+前缀和优化建图

显然，对于一条边的两个端点必须选择一个；对于一个块内的点，只能选择一个.

第一种限制好满足，第二个限制的话前/后缀和优化一下建图就行可.

code: 

#include <bits/stdc++.h>   
#define N 4000009   
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;    
stack<int>S;   
int n,m,K;  
int dfn[N],low[N],a[N],scc,cnt,tot;          
int hd[N],to[N<<1],nex[N<<1],id[N],inde[3][N],pre[N],suf[N],edges;   
void add(int u,int v) 
{
    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;   
}
void tarjan(int x) 
{
    S.push(x),dfn[x]=low[x]=++cnt;   
    for(int i=hd[x];i;i=nex[i]) 
    {
        int y=to[i]; 
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);  
        else if(!id[y]) low[x]=min(low[x],dfn[y]);   
    }
    if(low[x]==dfn[x]) 
    { 
        ++scc;  
        for(;;) 
        { 
            int u=S.top();S.pop();  
            id[u]=scc;  
            if(u==x) break;   
        }
    }
}               
int main() 
{ 
    // setIO("input");      
    int x,y,z; 
    scanf("%d%d%d",&n,&m,&K);  
    for(int i=1;i<=n;++i) inde[0][i]=++tot;  
    for(int i=1;i<=n;++i) inde[1][i]=++tot;  
    for(int i=1;i<=m;++i) 
    { 
        scanf("%d%d",&x,&y);         
        add(inde[0][x],inde[1][y]);  
        add(inde[0][y],inde[1][x]);    
    }
    for(int i=1;i<=K;++i) 
    {
        scanf("%d",&z);   
        for(int j=1;j<=z;++j) scanf("%d",&a[j]);      
        for(int j=1;j<=z;++j) 
        {
            pre[j]=++tot;     
            add(pre[j],inde[0][a[j]]);    
            if(j>1) add(pre[j],pre[j-1]);  
        }  
        for(int j=z;j>=1;--j) 
        {
            suf[j]=++tot;   
            add(suf[j],inde[0][a[j]]);  
            if(j<z) add(suf[j],suf[j+1]);  
        }
        for(int j=1;j<=z;++j) 
        {
            if(j>1) add(inde[1][a[j]],pre[j-1]);   
            if(j<z) add(inde[1][a[j]],suf[j+1]);  
        }    
    }   
    for(int i=1;i<=tot;++i)  if(!dfn[i]) tarjan(i);   
    for(int i=1;i<=n;++i) if(id[inde[0][i]]==id[inde[1][i]]) { printf("NIE
");  return 0; }   
    printf("TAK
");   
    return 0; 
}