#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e17*2;
const int N = 2e5 + 5;
vector<int> adj[N], low(N), in(N), vis(N), par(N), sz(N), sub(N), cl(N), clsz(N);
int timer = 0;
vector<pair<int, int> > bridge;
void dfs(int node, int par, int &cal, int &cnt){
vis[node] = 1;
in[node] = low[node] = timer++;
cl[node] = cal;
cnt++;
for(auto itr: adj[node]){
if(itr == par) continue;
if(vis[itr]){
low[node] = min(low[node], in[itr]);
}
else{
dfs(itr, node, cal, cnt);
low[node] = min(low[node], low[itr]);
if(in[node] < low[itr]){
bridge.pb(mp(min(node, itr), max(node, itr)));
}
}
}
}
int find(int a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b){
par[find(b)] = find(a);
}
vector<int> adj2[N];
void dfs2(int node, int &cnt){
cnt++;
vis[node] = 1;
for(auto itr: adj2[node]){
if(!vis[itr]){
dfs2(itr, cnt);
merge(node, itr);
}
}
}
vector<int> adjb[N];
void subcalc(int node, int par){
vis[node] = 1;
for(auto itr: adjb[node]){
if(itr != par){
subcalc(itr, node);
sub[node] += sub[itr];
}
}
sub[node] += sz[node];
}
void dfs3(int node, int par, int total, int &ans){
vis[node] = 1;
vector<int> v;
for(auto itr: adjb[node]){
if(itr != par) v.pb(sub[itr]);
}
if(node != par) v.pb(total - sub[node]);
for(auto itr: v){
ans += sz[node] * itr * (total - sz[node] - itr);
}
for(auto itr: adjb[node]){
if(itr != par){
dfs3(itr, node, total, ans);
}
}
}
void dfs4(int node, int par, int &val){
val += sz[node];
for(auto itr: adjb[node]){
if(itr == par) continue;
dfs4(itr, node, val);
}
}
int32_t main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
cin>>n>>m;
vector<pair<int, int> > edge(m);
for(int i = 0; i < m; i++){
int u, v;
cin>>u>>v;
if(u > v) swap(u, v);
edge[i] = mp(u, v);
adj[u].pb(v);
adj[v].pb(u);
}
int calss = 0;
for(int i = 1; i <= n; i++){
if(vis[i]) continue;
calss++;
int cnto = 0;
dfs(i, i, calss, cnto);
clsz[calss] = cnto;
}
sort(bridge.begin(), bridge.end());
sort(edge.begin(), edge.end());
int bind = 0;
for(int i = 0; i < m; i++){
if(bind < bridge.size() && bridge[bind] == edge[i]){
bind++;
continue;
}
auto[u, v] = edge[i];
adj2[u].pb(v);
adj2[v].pb(u);
}
for(int i = 1; i <= n; i++){
vis[i] = 0;
par[i] = i;
sz[i] = 1;
}
int cnt = 0, ans = 0;
for(int i = 1; i <= n; i++){
if(!vis[i]){
dfs2(i, cnt);
sz[i] = cnt;
ans += cnt * (cnt - 1) * (cnt - 2); // 3 here, 0 other
ans += (cnt - 1) * (cnt - 1) * (clsz[cl[i]] - cnt) * 2; // 2 here, 1 other
cnt = 0;
}
}
cout<<ans<<endl;
for(int i = 0; i < bridge.size(); i++){
auto[u, v] = bridge[i];
u = find(u), v = find(v);
adjb[u].pb(v);
adjb[v].pb(u);
}
for(int i = 1; i <= n; i++){
vis[i] = 0;
}
for(int i = 1; i <= n; i++){
if(vis[find(i)]) continue;
subcalc(find(i), find(i));
}
for(int i = 1; i <= n; i++){
vis[i] = 0;
}
for(int i = 1; i <= n; i++){
if(vis[find(i)]) continue;
int k = find(i);
int val = 0;
dfs4(k, k, val);
//cout<<i<<" -> "<<k<<" "<<val<<endl;
dfs3(k, k, val, ans);
}
cout<<ans<<endl;
return 0;
}
Compilation message
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:131:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(bind < bridge.size() && bridge[bind] == edge[i]){
| ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:157:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int i = 0; i < bridge.size(); i++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
48048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
38340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
38288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
26972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
