[AtCoder] ABC 204 C – Tour

2021年9月29日

問題

方針

スタートとゴールの組合せは最大でも \( N^2 \) であることが分かります．ある国から到達することが可能な国を探索するために必要な計算量は，同じ道を通る必要がないことを考慮して \( O(N + M)\) となります．したがって全ての頂点について調べます．

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    int A[M], B[M];
    vector<int> adj[N];
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        adj[A[i] - 1].push_back(B[i] - 1);
    }
    bool d[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            d[i][j] = false;
            if (i == j) d[i][j] = true;
        }
    }
    for (int i = 0; i < M; i++) {
        d[A[i] - 1][B[i] - 1] = true;
    }
    queue<int> q;
    bool flag[N];
    for (int i = 0; i < N; i++) {
        q.push(i);
        memset(flag, false, sizeof(flag));
        flag[i] = true;
        while (!q.empty()) {
            int v = q.front();
            d[i][v] = true;
            q.pop();
            for (int j : adj[v]) {
                if (!flag[j]) {
                    q.push(j);
                    flag[j] = true;
                }
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (d[i][j]) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}