Tamflexの貯蔵庫

やる気のない備忘録

abc 040

abc040.contest.atcoder.jp

union findを使いましょう.
新しい道からどんどん素集合データ構造を更新して行って,その時の各クエリが要求するノードが含まれる集合の濃度(要素数)を記憶,あとで出力すればとける.
unionfind自体は知っていてなんとなく使う気がしたけど,うまい人の解答をみてナルホドなぁと感じた.

これがクラスで

class UF
{
public:
  vector<int> parent;
  vector<int> rank;
  UF(){}
  UF(int n)
  {
    parent.resize(n);
    rank.resize(n,1);
    for(int i=0;i<n;i++) parent[i] = i;
  }
  int root(int x)
  {
    return x==parent[x]?x:parent[x]=root(parent[x]);
  }
  int size(int x)
  {
    return rank[root(x)];
  }
  void unite(int x, int y)
  {
    x=root(x);y=root(y);
    if(x==y) return;
    rank[x]+=rank[y];
    parent[y]=x;
  }
  bool same(int x, int y)
  {
    return root(x)==root(y);
  }
};

これが本体

int main()
{
  int n,m,q; scanf("%d %d",&n,&m);
  vector<tuple<int,int,int>> v;
  int a,b,y,id;
  REP(i,m)
  {
    scanf("%d %d %d",&a,&b,&y);
    v.push_back(make_tuple(-y,a-1,b-1));
  }
  scanf("%d",&q);
  vector<int> ans(q);
  REP(i,q)
  {
    scanf("%d %d",&a,&y);
    v.push_back(make_tuple(-y,i-1234567,a-1));
  }
  sort(v.begin(),v.end());
  UF uf(n);
  REP(i,v.size())
  {
    if(get<1>(v[i])<0)
    {
      tie(y,id,a)=v[i];
      id += 1234567;
      ans[id]=uf.size(a);
    }
    else
    {
      tie(std::ignore,a,b)=v[i];
      uf.unite(a,b);
    }
  }
  REP(i,q) printf("%d\n",ans[i]);
  return 0;
}