Submission #156091

#TimeUsernameProblemLanguageResultExecution timeMemory
156091IOrtroiii우호 조약 체결 (JOI14_friends)C++14
0 / 100
101 ms6740 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100100; int n, m; vector<int> g[N]; int par[N]; int sz[N]; bool visit[N]; int find(int v) { if (par[v] != v) { par[v] = find(par[v]); } return par[v]; } void merge(int v, int u) { v = find(v); u = find(u); if (v == u) { return; } else { par[u] = v; sz[v] += sz[u]; } } int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 1; i <= m; ++i) { int v, u; cin >> v >> u; g[v].emplace_back(u); } iota(par + 1, par + n + 1, 1); fill(sz + 1, sz + n + 1, 1); for (int i = 1; i <= n; ++i) { for (int j = 0; j + 1 < (int) g[i].size(); ++j) { merge(g[i][j], g[i][j + 1]); } } queue<int> q; for (int i = 1; i <= n; ++i) { if (sz[find(i)] > 1) { visit[i] = true; q.emplace(i); } } while (!q.empty()) { int v = q.front(); q.pop(); for (auto u : g[v]) { if (!visit[u]) { visit[u] = true; merge(v, u); q.emplace(u); } } } long long ans = 0; for (int i = 1; i <= n; ++i) { if (par[i] == i) { ans += (long long) sz[i] * (sz[i] - 1); } } for (int i = 1; i <= n; ++i) { for (int j : g[i]) { if (find(i) != find(j)) { ++ans; } } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...