首页 > 其他 > 详细

HDU3062 Party (2-SAT)

时间:2019-07-12 18:43:52      阅读:21      评论:0      收藏:0      [点我收藏+]

标签:hdu   ()   pre   -s   注意   lin   tar   ++   lse   

没注意边数T了N遍的我真是弱啊

const int N = 2007;

int n;

struct Edge{
    int nxt,pre;
}e[1000007];
int cntEdge,head[N];
inline void add(int u,int v){
    e[++cntEdge] = (Edge){head[u], v}, head[u] = cntEdge;
}

int dfn[N],dfnIndex,low[N],vis[N];
int sta[N],top;
int bcc[N],bccIndex;
inline void Tarjan(int u){
    dfn[u] = low[u] = ++dfnIndex;
    vis[u] = true;
    sta[++top] = u;
    for(register int i = head[u]; i; i = e[i].nxt){
        int v = e[i].pre;
        if(!dfn[v]){
            Tarjan(v);
            low[u] = Min(low[u], low[v]);
        }
        else if(vis[v]){
            low[u] = Min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        ++bccIndex;
        do{
            bcc[sta[top]] = bccIndex;
            vis[sta[top]] = false;
        }while(sta[top--] != u);
    }
    
}

inline bool Judge(){
    R(i,1,n){
        if(bcc[i<<1] == bcc[i<<1|1])
            return false;
    }
    return true;
}
int main(){
    int m;
    while(~scanf("%d%d", &n, &m)){
        cntEdge = 0;
        n <<= 1;
        R(i,1,n){
            head[i] = 0,
            dfn[i] = 0,
            low[i] = 0,
            vis[i] = false;
        }
        n >>= 1;

        R(i,1,m){
            int a,b,c,d;
            io >> a >> b >> c >> d;
            a = (a<<1) + c;
            b = (b<<1) + d;
            add(a, b ^ 1);
            add(b, a ^ 1);
        }
        
        n <<= 1;
        R(i,1,n){
            if(!dfn[i])
                Tarjan(i);
        }
        n >>= 1;
        
        if(Judge() == true)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

HDU3062 Party (2-SAT)

标签:hdu   ()   pre   -s   注意   lin   tar   ++   lse   

原文:https://www.cnblogs.com/bingoyes/p/11177706.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号