[AtCoder] ABC 204 C – Tour
問題
方針
スタートとゴールの組合せは最大でも \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません