为什么全RE,快来救救孩子吧
查看原帖
为什么全RE,快来救救孩子吧
1030602
yi_qing楼主2023/8/19 18:13

不使用快读就过不去了吗

#include<iostream>
using namespace std;

const int N = 1e6+5;

int tot,head[N*2];
struct{
    int to,next;
}edge[4*N];
void add(int u,int v){
    tot++;
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot; 
}

int low[N<<1],num[N<<1],st[N<<1],sccno[N<<1],dfn,top,cnt;
int n,m;
void tarjan(int u){
    st[top--] = u;
    low[u] = num[u] = ++dfn;
    for(int i=head[u];i>0;i=edge[i].next){
        int v = edge[i].to;
        if(!num[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u]= min(low[u],num[v]);
        }
    }
    if(low[u] == num[u]){
        cnt++;
        while(1){
            int v = st[--top];
            sccno[v] = cnt;
            if(u==v) break;
        }
    }
    return;
}
bool two_sat(){
    for(int i=1;i<=2*n;i++){
        if(!num[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        if(sccno[i] == sccno[i+n])//非a和a在一个强连通分量里;
        return false;
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int a,b,va,vb;scanf("%d%d%d%d",&a,&va,&b,&vb);
        int nota = va^1,notb = vb^1;
        add(a+nota*n,b+vb*n);
        add(b+notb*n,a+va*n);
    }
    if(two_sat()){
        printf("POSSIBLE\n");
        for(int i=1;i<=n;i++)printf("%d",sccno[i]>sccno[i+n]);
        
    }
    else printf("IMPOSSIBLE");
    return 0;
}
2023/8/19 18:13
加载中...