A. Union of Doubly Linked Lists

• Quiz
  • https://codeforces.com/problemset/problem/847/A
• AC
  • https://codeforces.com/contest/847/submission/100729004
• 解説
  • editorialがないので書いておこうと思ったが、実装問題です。特殊なデータ構造は不要
  • 左右の情報が与えられるので、各数字の右と左を答えられるようにしておく
  • サンプルでいうと左端集合は6,3,5なので「6から始まるリスト」＋「3から始まるリスト」＋「5から始まるリスト」と連結すればいい

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    // iがどこから来たか
    VI from(N,-1);
    // iがどこへ行くか
    VI to(N,-1);
    
    rep(i,N){
      ll l,r;cin>>l>>r;
      l--;r--;
      if(l!=-1){
        from[i]=l;
      }
      if(r!=-1){
        to[i]=r;
      }
    }

    // 左端集合
    VI lefts;
    rep(i,N){
      if(from[i]==-1)lefts.push_back(i);
    }

    VI A;
    for(ll left : lefts){
      A.push_back(left);
      while(to[A.back()]!=-1){
        ll nxt = to[A.back()];
        A.push_back(nxt);
      }
    }

    // value to index
    VI I(N);
    rep(i,N){
      ll a = A[i];
      I[a]=i;
    }

    rep(a,N){
      ll idx = I[a];
      ll left=-1;
      ll right=-1;
      if(idx)left=A[idx-1];
      if(idx<N-1)right=A[idx+1];
      p2(left+1,right+1);
    }
    
    return 0;
}