输入出现问题 RE on #7 - #10
查看原帖
输入出现问题 RE on #7 - #10
568884
AFLeartLey0103楼主2022/9/2 11:56

这份代码是可以通过 #1 - #6 的,但在 #7 - #10 出现了读入的数有误的情况

我自己本地测试时也出现了文件内容和读入的数不同的诡异情况(n=0 m=16) 求教是什么原因

#include<bits/stdc++.h>
using namespace std;
#define maxn 200050
int n;
namespace Tsat{
    namespace tarjan{
        vector<int> E[maxn];
        int scc[maxn],sc,tstamp;
        stack<int> st;
        int stat[maxn],dfn[maxn],low[maxn];
        void dfs(int p){
            dfn[p] = low[p] = ++tstamp;
            stat[p] = 1;
            st.push(p);
            for(auto i:E[p]){
                if(!stat[i]){
                    dfs(i);
                    low[p] = min(low[i],low[p]);
                }
                else if(stat[i] == 1)
                    low[p] = min(low[p],dfn[i]);
            }
            if(dfn[p] == low[p]){
                int stop;
                sc++;
                do{
                    stop = st.top();
                    st.pop();
                    stat[stop]=2;
                    scc[stop] = sc;
                }while(stop != p);
            }
        }
        void work(){
            for(int i = 1;i<=n<<1;++i){
                if(!stat[i])dfs(i);
            }
        }
    }
    void addedge00(int a,int b){
        tarjan::E[a].push_back(b+n),tarjan::E[b].push_back(a+n);
    }
    void addedge11(int a,int b){
        tarjan::E[a+n].push_back(b),tarjan::E[b+n].push_back(a);
    }
    void addedge01(int a,int b){
        tarjan::E[a].push_back(b),tarjan::E[b+n].push_back(a+n);
    }
    void addedge10(int a,int b){
        tarjan::E[a+n].push_back(b+n),tarjan::E[b].push_back(a);
    }
    void work(){
        tarjan::work();
        for(int i = 1;i<=n;++i){
            if(tarjan::scc[i] == tarjan::scc[i+n]){
                std::cout<<"IMPOSSIBLE";
                return;
            }
        }
        std::cout<<"POSSIBLE\n";
        for(int i = 1;i<=n;++i){
            std::cout << (tarjan::scc[i]<tarjan::scc[i+n] ? 1 : 0) << ' ';
        }
    }
}
signed main(){
    int m;
    std::cin >> n >> m;
    for(int i = 0;i<m;++i){
        int x,a,y,b;
        std::cin >> x >> a >> y >> b;
        if(a){
            if(b)Tsat::addedge11(x,y);
            else Tsat::addedge10(x,y);
        }
        else{
            if(b)Tsat::addedge01(x,y);
            else Tsat::addedge00(x,y);
        }
    }
    Tsat::work();
    return 0;
}
2022/9/2 11:56
加载中...