AtCoder 勉強記録[C++] その63

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
私のアカウント
解いた問題

本日解いた問題

C - Ladder Takahashi

C - Ladder Takahashi
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

map<int, vector<int>> g;
set<int> seen;
void dfs(int v){
  seen.insert(v);
  for(auto nex:g[v]){
    if(seen.count(nex)) continue;
    dfs(nex);
  }
  
}

int main() {
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1);
  cout << *seen.rbegin() << endl;
}

解法

問題のビルが10^9階建てであるため、全てを考えると計算量をオーバーしてしまう。ここで、はしごの数は2*10^5個であるため、はしごのかかった階のみを考えることで計算量を減らす。今回はMap型を用いることではしごのかかった階のみを考える。さらにDFSを用いることで結果がもとまる。

C - FF

C - FF
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  int n, q;
  cin >> n >> q;
  set<pair<int, int>> f;
  for(int i = 0; i < q; i++){
    int a, b, t;
    cin >> t >> a >> b;
    if(t == 1){
      f.emplace(a,b);
    } else if(t == 2) {
      f.erase({a,b});
    } else {
      if(f.count({a,b}) && f.count({b,a})) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
}

解法

AがBをフォローしている関係をpair型配列を用いて(A,B)と表す。この関係を管理するset型を用意しておき、T=1の場合は(A,B)を追加、T=2の場合は(A,B)を削除、T=3の場合は(A,B)、(B,A)ともに存在する場合Yesを、存在しない場合Noを出力する。