ABC157「Friend Suggestions」

Friend Suggestions

考えたこと

• ぱっと見難しくはなさそう（解けなかったんだけどね）

• 友達候補の条件を読む

  • 最後の条件が複雑だけどちゃんと読むと、a, bが連結成分上にあればいいってことが書いてある（最初これ読んでなくて死んだ）

• なんかよくわかんなくて終了

解法

1. 求めたいものを明確にする
   • 条件を読むと、友達候補の数は「連結成分の大きさ - 連結成分上の友達の数 - 連結成分上のブロックの数」になることがわかる
   • なので、連結成分の大きさ、連結成分上の友達の数、連結成分上のブロックの数がわかれば解ける
2. 連結成分の大きさを求める
   • DFSで節点にラベルをつける。同じ連結成分上にある接点のラベルは同じ値っていう設定
   • ここの計算量ちょっとわかんないけど、TLEにはならない（頭いい人教えて...）
3. 答えを求める
   • 答えはこれ→連結成分の大きさ - 連結成分上の友達の数 - 連結成分上のブロックの数
   • 連結成分上の友達の数は、普通に友達の数でOK
   • 連結成分上のブロックの数は、ラベルが同じかを比較すれば判定できる
   • ってこととで解ける

コード

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int A[111111];
int B[111111];
int C[111111];
int D[111111];
vector<int> F[111111];
vector<int> bl[111111];
int label[111111]; // 節点iのラベルはlebel[i]
map<int, int> label_cnt; // label[l]: ラベルlの連結成分の大きさ

// 連結成分の大きさを求める
int dfs(int now, int l) {
    label[now] = l;

    int ret = 0;
    for (int child : F[now]) {
        if (label[child] != 0) continue;
        ret += dfs(child, l) + 1;
    }

    return ret;
}

int main() {
    // 入力
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
        F[A[i]].push_back(B[i]);
        F[B[i]].push_back(A[i]);
    }

    for (int i = 0; i < K; i++) {
        cin >> C[i] >> D[i];
        C[i]--, D[i]--;
        bl[C[i]].push_back(D[i]);
        bl[D[i]].push_back(C[i]);
    }

    int l = 1; // ラベル番号
    for (int i = 0; i < N; i++) {
        if (label[i] != 0) continue;
        label_cnt[l] = dfs(i, l) + 1;
        l++;
    }

    for (int i = 0; i < N; i++) {
        int ans = label_cnt[label[i]] - 1 - F[i].size();
        for (int b : bl[i]) {
            if (label[b] == label[i]) {
                ans--;
            }
        }
        cout << ans << " ";
    }
    cout << endl;
}

感想

• 同じグループのものにラベルをつけるって発想がなかった
  • 言われてみれば当たり前なんだけどね。なんで思いつかないんだろうね
  • ラベルつけたら、同じグループかどうかを一瞬で判定できるから強い
• Union Findでも解ける
  • 気力ないからねる
  • Union Find使ってないのにタグつけちゃったごめん