Sto provando a fare il problema flood, la mia soluzione consiste in:
dsu su i quattro quadratini che uniscono un vertice per costruire il grafo e poi una bfs che parte ogni volta dal nodo più in alto non visitato.
Non riesco a trovare testcase che sbaglino però submittando sbaglia circa la metà dei casi.
Qualcuno potrebbe aiutarmi a trovare l’errore?
using namespace std;
int uf[400000];
int siz[400000];
bool vis[400000],pres[400000];
int tim[400000];
bool sos[400000];
vector<pair<int,int>> adjj[400000];
int find(int a){
if(uf[a]!=a)uf[a]=find(uf[a]);
return uf[a];
}
void uni(int a,int b){
a = find(a); b = find(b);
if(siz[a]>siz[b])swap(a,b);
uf[a]=b;
siz[b]+=siz[a];
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int N,K,a,b;
for(int i = 0; i < 400000; i++){siz[i]=1;uf[i]=i;}
cin >> N;
int cx[N];
int cy[N];
int curr = N-1;
vector<pair<int,int>> adj[N];
for(int i = 0; i < N; i++)scanf("%d %d",&cx[i],&cy[i]);
scanf("%d",&K);
vector<pair<int,int>> pts;
for(int i = 0; i < N; i++)pts.push_back({cy[i],i});
sort(pts.begin(),pts.end());
int walls[K][2],arcs[K][2];
for(int i = 0; i < K; i++){
scanf("%d %d",&a,&b);
adj[a-1].push_back({b-1,i});
adj[b-1].push_back({a-1,i});
arcs[i][1]=a-1; arcs[i][0]=b-1;
}
int sas[4];
int x,y;
for(int i = 0; i < N; i++){
sas[0]=-1;sas[1]=-1;sas[2]=-1;sas[3]=-1;
for(auto k: adj[i]){
x=k.first; y=k.second;
if(cx[x]==cx[i]){
if(cy[x]>cy[i]){sas[0]=x;walls[y][0]=i;walls[y][1]=i+100000;}
else sas[2]=x;
}else{
if(cx[x]>cx[i]){sas[1]=x;walls[y][0]=i+100000;walls[y][1]=i+200000;}
else sas[3]=x;
}
}
if(sas[0]==-1){uni(i,i+100000);}
else{uni(i,sas[0]+300000); uni (i+100000,sas[0]+200000);}
if(sas[1]==-1){uni(i+100000,i+200000);}
else{uni(i+100000,sas[1]);uni(i+200000, sas[1]+300000);}
if(sas[2]==-1){uni(i+200000,i+300000);}
else{uni(i+300000,sas[2]);uni(i+200000,sas[2]+100000);}
if(sas[3]==-1){uni(i,i+300000);}
else{uni(i,100000+sas[3]);uni(i+300000,sas[3]+200000);}
}
for(int i = 0;i < K;i++){
a=find(walls[i][0]); b=find(walls[i][1]);
adjj[a].push_back({b,i});
adjj[b].push_back({a,i});
}
for(int i = 0; i < 400000; i++){vis[i]=0; pres[i]=0;tim[i]=-1;sos[i]=0;}
queue <pair<int,int>> q;
int t,node,res=K;
bool sus = true;
do{
if(q.empty()){
while(sos[curr] && curr >= 0)curr--;
if(curr < 0){sus=false;break;}
q.push({find(pts[curr--].second),t});
}
node = q.front().first;
t = q.front().second;
q.pop();
if(vis[node])continue;
vis[node]=1;
for(auto x: adjj[node]){
sos[arcs[x.second][0]]=1;
sos[arcs[x.second][1]]=1;
if(!vis[x.first]&&tim[x.first]!=t){
q.push({x.first,t+1});
res--;
tim[x.first]=t+1;
pres[x.second]=1;
}
}
}while(sus);
cout << res << "\n";
for(int i = 0; i < K; i++)if(pres[i]==0)cout<<i+1<<"\n";
return 0;
}
