这份代码是可以通过 #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;
}