If it suits your application then turning @sets into %sets gives a useful performance gain:

use strict;
use warnings;
use Time::HiRes qw[ time ];
use List::Util qw[ shuffle ];

our $N //= 1e3;
our $S //= 1e4;
our $Z //= 5;

my %flags = map {$_ => []} 1 .. $N;
my %sets = map {$_ => [map 1 + int(rand $N), 1 .. 1 + int(rand $Z)]} 1
+ .. $S;
my $start = time;
for my $set (keys %sets) {
    next if ! @{$sets{$set}};
    push @{$flags{$_}}, $set for @{$sets{$set}};
}
printf "Setup: %.6fs\n", time() - $start;

my @someOrder = shuffle 1 .. $N;

$start = time();
for my $flag (@someOrder) {
    for my $set (@{$flags{$flag}}) {
        $sets{$set} = [grep {$_ != $flag} @{$sets{$set}}];
        next if @{$sets{$set}};
        delete $sets{$set};
    }
}
printf "Took: %.6fs\n", time() - $start;
[download]

Prints:

Setup: 0.037229s
Took: 0.077418s
[download]