読者です 読者をやめる 読者になる 読者になる

AtCoder Typical Contest 001 復習

はい。
http://atc001.contest.atcoder.jp/

A - 深さ優先探索

スタートからゴールまで到達できるか、後で書く

B - Union Find

N個の頂点のグラフにQ個のクエリが与えられて連結処理や、連結しているかの判定をUnion Findで。

python

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#roitiさんをまるまるパクリ
import time
import sys
import io
import re
import math
import itertools
import collections
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
#start = time.clock()
class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par=range(size)
        self.g_num=size

    def find(self, x):
    #木の根を求める
        if x==self.par[x]:
        #根
            return x
        #経路圧縮
        self.par[x]=self.find(self.par[x])
        return self.par[x]

    def same(self, x, y):
    #xとが同じ集合に属するか否か
        return self.find(x)==self.find(y)

    def unite(self, x, y):
    #xとyの属する集合を併合
        x,y=self.find(x),self.find(y)
        if x==y:
            return

        self.g_num-=1
        if self.rank[x]>self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def group_num(self):
        return self.g_num


N,Q=map(int,raw_input().split())
uf=UnionFind(N)

for loop in xrange(Q):
    p,a,b=map(int,raw_input().split())
    if p==0:
        uf.unite(a,b)
    else:
        print 'Yes' if uf.same(a,b) else 'No'

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
 
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unite(int x, int y){
        x=root(x), y=root(y);
        if(x!=y){
            if(data[y]<data[x]){
                swap(x,y);
            }
            data[x]+=data[y], data[y]=x;
        }
        return x!=y;
    }
 
    bool find(int x, int y){
        return root(x)==root(y);
    }
 
    int root(int x){
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
 
    int size(int x){
        return -data[root(x)];
    }
};
 
 
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    UnionFind uf(n);
    for(int i=0;i<q;i++){
        int p,a,b;
        scanf("%d %d %d",&p,&a,&b);
        if(p!=0){
            if(uf.find(a,b)){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }else{
            uf.unite(a,b);
        }
    }
    return 0;
}

C++11よくわからん。。。また後で