有没有巨佬帮忙看看为什么样例没过,但是AC了
#include<bits/stdc++.h>
using namespace std;
const int N=8e6+10;
int n,tot,tr[N][2],cnt,step,low[N],dfn[N],col[N];
string s[N];
vector<int> g[N];
stack<int> st;
bool vis[N];
void tarjan(int x){
dfn[x]=++step; low[x]=dfn[x];
st.push(x); vis[x]=1;
for(int v:g[x]){
if(!dfn[v]){
tarjan(v); low[x]=min(low[x],low[v]);
}else if(vis[v]) low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
++cnt; int y;
do{
y=st.top(); st.pop();
col[y]=cnt; vis[y]=0;
}while(y!=x);
}
}
void dfs(int x){
if(tr[x][0]) dfs(tr[x][0]);
if(tr[x][1]) dfs(tr[x][1]);
bool flag=0;
for(int i=0;i<g[x-2].size();i++){
int v=g[x-2][i];
if(v==x) continue;
if(flag){
if(v>n) g[v-n].push_back(tot-1);
else g[v+n].push_back(tot-1);
g[tot].push_back(v);
}
g[++tot].push_back(v);
if(v>n) g[v-n].push_back(++tot);
else g[v+n].push_back(++tot);
if(flag){
g[tot-1].push_back(tot-3);
g[tot-2].push_back(tot);
}
flag=1;
}
flag=0;
for(int i=g[x-2].size()-1;i>=0;i--){
int v=g[x-2][i];
if(v==x) continue;
if(flag){
if(v>n) g[v-n].push_back(tot-1);
else g[v+n].push_back(tot-1);
g[tot].push_back(v);
}
g[++tot].push_back(v);
if(v>n) g[v-n].push_back(++tot);
else g[v+n].push_back(++tot);
if(flag){
g[tot-1].push_back(tot-3);
g[tot-2].push_back(tot);
}
flag=1;
}
}
void ins(int x,int op){
int p=2*n+3;
for(int i=0;i<s[x].size();i++){
int c=s[x][i];
if(c!='0'&&c!='1') c=op;
else c=c-'0';
if(!tr[p][c]){
tr[p][c]=tot+3;
g[p].push_back(++tot);
g[++tot].push_back(p+1);
g[tot-1].push_back(++tot);
g[++tot].push_back(tot-2);
}
p=tr[p][c];
}
g[x+op*n].push_back(p);
g[p+1].push_back(x+(op^1)*n);
g[p-2].push_back(x+(op^1)*n);
g[x+op*n].push_back(p-1);
}
int main(){
scanf("%d",&n); tot=2*n+4;
g[2*n+1].push_back(2*n+3);
g[2*n+4].push_back(2*n+2);
for(int i=1;i<=n;i++){
cin>>s[i]; ins(i,0); ins(i,1);
}
dfs(2*n+3);
for(int i=1;i<=tot;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;i++){
if(col[i]==col[i+n]){
cout<<"NO"<<"\n";
return 0;
}
}
for(int i=n*2+1;i<tot;i+=2){
if(col[i]==col[i+1]){
cout<<"NO"<<"\n";
return 0;
}
}
cout<<"YES"<<"\n";
for(int i=1;i<=n;i++){
for(int j=0;j<s[i].size();j++){
if(s[i][j]=='?') cout<<(col[i]>col[i+n]);
else cout<<s[i][j];
}
cout<<"\n";
}
return 0;
}
输出
YES
000
0100
01
100