这段代码是我本题的整体二分部分的实现,我认为没有问题但无法通过此题,改成题解的逻辑就能通过了,但我认为我的逻辑没有问题,求大佬答疑。
inline void solve (int l,int r,std :: vector <node> es) {
if (l == r) {
for (auto E : es)
cn[l].emplace_back (E.u , E.v) ;
return ;
}
int mid = (l + r) >> 1;
std :: vector <node> ls , rs;
for (auto E : es)
if (E.t > mid)
scc :: adde (dsu :: find(E.u) , dsu :: find(E.v));
scc :: solve () ;
int tim = dsu :: op ;
for (auto E : es) {
if (E.t > mid) {
if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)])
ls.push_back (E) ; // 如果只加入后面的边不能连通,放到左边寻找更靠前的时间。
else
dsu :: merge (dsu :: find(E.u) , dsu :: find(E.v)) ,
rs.push_back (E) ; // 如果之加入后面的边已经连通了,放到右边寻找更靠后的时间,同时将连通性以并查集的形式放到左边。
}
else {
if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)])
ls.push_back (E) ; // 没有连通,试图寻找更左边的时间是否连通 。
else
cn[E.t].emplace_back (E.u , E.v) ; // 如果只加入了 mid右边这些边都连通了,那么加入这条边的时候它的左右就一定连通了,不继续下放。
}
}
scc :: clear () ;
solve (l , mid , ls) ;
dsu :: recall (tim) ;
solve (mid + 1 , r , rs) ;
}
这是题解下放部分的逻辑
for (auto E : es) {
if (E.t > mid) {
if (scc :: bel[dsu :: find(E.u)] != scc :: bel[dsu :: find(E.v)])
ls.push_back (E) ; // 如果只加入后面的边不能连通,放到左边寻找更靠前的时间。
else
dsu :: merge (dsu :: find(E.u) , dsu :: find(E.v)) ,
rs.push_back (E) ; // 如果之加入后面的边已经连通了,放到右边寻找更靠后的时间,同时将连通性以并查集的形式放到左边。
}
else {
ls.push_back (E) ; // 以为是再更左边出现的,所以不管连不连通直接丢给左边。
}
}