#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 2;
ll ans = 0;
int num[N + 2], low[N + 2], timer , n , m , scc;
stack < int > st;
vector < int > adj[N + 2] , g[N + 2];
ll sz[N + 2];
int mN;
void dfs(int u , int p = - 1){
low[u] = num[u] = ++timer;
st.push(u);
for(auto v: adj[u]){
if(v == p)continue;
if(!num[v]){
dfs(v , u);
low[u] = min(low[u] , low[v]);
if(low[v] >= num[u]){
scc ++;
g[scc].push_back(u);
g[u].push_back(scc);
int y;
do{
y = st.top();
st.pop();
g[y].push_back(scc);
g[scc].push_back(y);
}while(y != v);
}
}
else{
low[u] = min(low[u] , num[v]);
}
}
}
ll cal(ll total_square , ll total , ll er){
total_square -= er * er;
total -= er;
return total * total - total_square;
}
ll three_im(ll x , ll z){
if(x < z)return 0;
ll k = 1;
for(ll i = x ;i >= x - z + 1; i --){
k *= i;
}
return k ;
}
void dfs2(int u , int p = - 1){
if(u <= mN)sz[u] ++;
for(auto v: g[u]){
if(v == p)continue;
dfs2(v , u);
sz[u] += sz[v];
}
if(u > mN){
ans -= three_im(g[u].size() - 1, 2) * (mN - sz[u] - 1);
return ;
}
ll oth = mN - sz[u] ;
ll total_square = 0;
ll total = 0;
for(auto v: g[u]){
if(v == p) continue;
total_square += sz[v] * sz[v];
total += sz[v];
}
total_square += oth * oth;
total += oth;
ans -= cal(total_square , total , 0) * 2;
for(auto v: g[u]){
if(v == p)continue;
ans -= cal(total_square , total , sz[v]);
}
ans -= cal(total_square , total , oth);
}
void solve() {
cin >> n >> m;
scc = n;
for(int i = 1; i <= m ; i ++){
int u , v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= n ; i++){
if(!num[i]){
mN = timer;
dfs(i);
mN = timer - mN;
ans += three_im(mN, 3);
dfs2(i);
}
}
cout << ans;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
#define _ "minrect."
if (fopen(_ "inp", "r")) {
freopen(_ "inp", "r", stdin);
freopen(_ "out", "w", stdout);
}
solve();
}
Compilation message
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen(_ "inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen(_ "out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
32056 KB |
Output is correct |
| 2 |
Correct |
42 ms |
31952 KB |
Output is correct |
| 3 |
Incorrect |
47 ms |
28580 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
22364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
22356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
