AtCoder Typical Contest 001 復習
はい。
http://atc001.contest.atcoder.jp/
A - 深さ優先探索
スタートからゴールまで到達できるか、後で書く
B - Union Find
N個の頂点のグラフにQ個のクエリが与えられて連結処理や、連結しているかの判定をUnion Findで。
#!/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よくわからん。。。また後で