AtCoder ABC 177 D - Friends (400点)

https://gyazo.com/c9fa77d3cec7290d7b2e1f7596672488

https://atcoder.jp/contests/abc177/tasks/abc177_d

Union-Findアルゴリズム, 典型問題, グラフ, 連結成分

考察履歴

グラフで友達関係を図示

XとYが友達、かつ、YとZが友達ならば、X とZも友達

要するに友達の友達も友達

つまり友達同士のグループを作り、最大グループのサイズが答えになる

最大グループのメンバを全員異なるグループにすれば、「同じグループの中に友達がいない」という状況が作れる

最大グループ以下のサイズのメンバは適当に割り振れば良い

このグループサイズを計算する方法がわからずコンテスト本番ではACできず。。解説AC

素集合データ構造でUnion-Findアルゴリズムを利用することで、サイズまでを高速に計算できる

ToDo幅優先探索の連結成分を調べても解答可能なよう

ACコード

code:cpp

#include <iostream>

#include <algorithm>

#include <vector>

#include <array>

#include <iomanip>

#include <set>

using namespace std;

typedef long long ll;

#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)

#define REPD(i,n) for(ll i=n-1;i>=0;i--)

#define SORT(s) sort((s).begin(),(s).end())

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

struct UnionFind{

//ノード情報のベクトル。

//各ノードは親のノードを指す。

//根なら木のサイズを負にして入れる。

vector<int> d;

//コンストラクタ dをn個の要素でそれぞれサイズ-1で初期化

UnionFind(int n=0): d(n,-1){}

//属する木のグループ番号を返す

//実態は属する木の根のノード番号

int find(int x){

if(dx < 0) return x;

return dx = find(dx);

}

//木の併合

//木のサイズが小さい方を大きい方にくっつける

//長いものにまかれにいく

//木が深くならなくなる

bool unite(int x, int y){

//所属するグループの検索

x = find(x); y = find(y);

//すでに所属グループが同じ

if(x==y) return false;

//xを大きいサイズのグループに設定する

if(-dx < -dy) swap(x,y);

//大きいグループxに小さいグループyをくっつける

dx += dy;

//グループyの親をxにする

dy = x;

return true;

}

//ノードxとノードyが同じグループか判定する

bool same(int x, int y) { return find(x) == find(y);}

//所属するグループのサイズを返す

int size(int x) { return -dfind(x);}

};

int main(){

ll N,M; cin >> N >> M;

UnionFind tree(N);

REP(i,M){

int a,b;

cin >> a >> b;

tree.unite(a-1,b-1);

}

int ans = 0;

REP(i,N){

ans = max(ans,tree.size(i));

}

cout << ans << endl;

return 0;

}

Difficulty 600 676、茶diff

これは茶diffなのか。。。Union-Find知っていれば簡単ではあるが。。なるほど。