AtCoder Typical Contest 001 参加 - アルゴリズムのメモ帳

Cの高速フーリエ変換だけ分からなかった。。高速フーリエ変換ちゃんと勉強しよっと。。

A: 深さ優先探索

int H, W;
string mp[505] = {};
bool used[505][505] = {};
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve(int x, int y) {
    used[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (0 <= nx && nx < H && 0 <= ny && ny < W) {
            if (!used[nx][ny]) {
                solve(nx, ny);
            }
        }
    }
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> mp[i];
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == '#') {
                used[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == 's') {
                solve(i, j);
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == 'g') {
                if (used[i][j]) {
                    cout << "Yes" << endl;
                } else {
                    cout << "No" << endl;
                }
            }
        }
    }
    return 0;
}

B: Union Find

struct UF {
    vector<int> parent, rank;
 
    UF(int n) {
        parent.resize(n); rank.resize(n);
        for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; }
    }
 
    bool same(int x, int y) {
        return (find_root(x) == find_root(y));
    }
 
    int find_root(int x){
        if (parent[x] != x) parent[x] = find_root(parent[x]);
        return parent[x];
    }
 
    void connect(int x, int y){
        int rx = find_root(x), ry = find_root(y);
        if (rx == ry) return;
        if (rank[rx] > rank[ry]) { parent[ry] = rx; rank[rx] += rank[ry]; }
        if (rank[rx] <= rank[ry]) { parent[rx] = ry; rank[ry] += rank[rx]; }
    }
};
 
 
int main() {
    int N, Q;
    cin >> N >> Q;
    UF uf(N);
    for (int i = 0; i < Q; i++) {
        int p, a, b;
        cin >> p >> a >> b;
        if (p) {
            if (uf.same(a, b)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } else {
            uf.connect(a, b);
        }
    }
    return 0;
}