Submission #6915

#TimeUsernameProblemLanguageResultExecution timeMemory
6915tncks0121우호 조약 체결 (JOI14_friends)C++98
0 / 100
124 ms8320 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <deque> #include <utility> #include <bitset> #include <limits.h> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; typedef pair<ll, int> pli; #define pb push_back const int N_ = 100005; int N, M; vector<int> Gph[N_]; bool visited[N_]; namespace DS { int group[N_], sz[N_]; void init () { for(int i = 1; i <= N; i++) group[i] = i, sz[i] = 1; } int get_group (int v) { return (group[v] == v) ? v : (group[v] = get_group(group[v])); } int merge (int u, int v) { u = get_group(u); v = get_group(v); if(u == v) return false; sz[v] += sz[u]; sz[u] = 0; group[u] = v; return true; } }; void dfs (int u, int l = -1) { visited[u] = true; for(int e = 0; e < Gph[u].size(); e++) { int v = Gph[u][e]; if(l != -1) DS::merge(l, v); l = v; if(!visited[v]) dfs(v, u); } } ll res; int main() { scanf("%d%d", &N, &M); for(int i = 1; i <= M; i++) { int u, v; scanf("%d%d", &u, &v); Gph[u].pb(v); } DS::init(); for(int i = 1; i <= N; i++) { if(!visited[i] && Gph[i].size() >= 2) dfs(i); } for(int i = 1; i <= N; i++) res += (ll)DS::sz[i] * (DS::sz[i] - 1); for(int i = 1; i <= N; i++) { for(int e = 0; e < Gph[i].size(); e++) { int j = Gph[i][e]; int a = DS::get_group(i), b = DS::get_group(j); if(a != b) ++res; } } printf("%lld\n", res); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...