Submission #14701

#TimeUsernameProblemLanguageResultExecution timeMemory
14701gs14004우호 조약 체결 (JOI14_friends)C++14
0 / 100
110 ms7208 KiB
#include <cstdio> #include <vector> using namespace std; struct disj{ int pa[100005], sz[100005]; void init(int n){ for(int i=1; i<=n; i++) pa[i] = i, sz[i] = 1; } int find(int x){ if(pa[x] == x) return x; return pa[x] = find(pa[x]); } int uni(int p, int q){ p = find(p); q = find(q); if(p == q) return 0; pa[q] = p; sz[p] += sz[q]; return 1; } }disj; bool vis[100005]; int n,m; vector<int> g[100005]; int main(){ scanf("%d %d",&n,&m); disj.init(n); for (int i=0; i<m; i++) { int x,y; scanf("%d %d",&x,&y); g[x].push_back(y); } for (int i=1; i<=n; i++) { for (int j=0; j+1<g[i].size(); j++) { disj.uni(g[i][j],g[i][j+1]); } } for (int i=1; i<=n; i++) { if(disj.sz[disj.find(i)] != 1 && !g[i].empty()){ disj.uni(i,g[i][0]); } } long long ret = 0; for (int i=1; i<=n; i++) { if(!vis[disj.find(i)]){ vis[disj.find(i)] = 1; ret += 1ll * disj.sz[disj.find(i)] * (disj.sz[disj.find(i)] - 1); } } for (int i=1; i<=n; i++) { for (int &j : g[i]){ if(disj.find(i) != disj.find(j)) ret++; } } printf("%lld",ret); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...