This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long n, m, x, y, vis[300000], ans;
vector <int> t[300000];
void DFS (int v){
vis[v] = 1;
for (auto i : t[v]){
if (vis[i] == 0){DFS(i);vis[v] += vis[i];
}
}
}
void dfs (int v, int r, int p = 0){
ans+=(vis[r]-vis[v])*(vis[v]-1)*2;
for (auto i : t[v]){
if (i != p){dfs(i, r, v);ans+=(vis[v]-vis[i]-1)*vis[i];}
}
}
main() {
cin >> n >> m;
for(int i = 0;i < m;i++){
cin >> x >> y;
x--;
y--;
t[x].push_back(y);
t[y].push_back(x);
}
for (int i = 0; i < n; i++){
if (vis[i] == 0){
DFS(i);
dfs(i, i);
}
}
cout << ans;
}
Compilation message (stderr)
count_triplets.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |