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;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
vector<int> adj[maxn], nadj[maxn];
int in[maxn], low[maxn], sq[maxn], sz[maxn], dfn = 0, cnt = 0;
int n, m, ans = 0;
stack<int> st;
void dfs(int pos){
in[pos] = low[pos] = ++dfn;
st.push(pos);
for(auto x : adj[pos]){
if(in[x]) low[pos] = min(low[pos], in[x]);
else{
dfs(x);
if(low[x] >= in[pos]){
int cur = n++;
sq[cur] = 1, in[cur] = 1;
while(st.top() != pos){
nadj[cur].pb(st.top());
nadj[st.top()].pb(cur);
st.pop();
}
nadj[cur].pb(pos);
nadj[pos].pb(cur);
int sz = nadj[cur].size();
}
}
}
}
void dfs2(int pos, int prev){
sz[pos] = 1 - sq[pos];
for(auto x : nadj[pos]){
if(x == prev) continue;
dfs2(x, pos);
sz[pos] += sz[x];
}
}
void dfs3(int pos, int prev, int tsz){
// cout<<"d : "<<tsz<<" "<<pos<<" "<<sz[pos]<<"\n";
if(!sq[pos]){
ans += (tsz - 1) * (tsz - 1);
ans -= (tsz - sz[pos]) * (tsz - sz[pos]);
for(auto x : nadj[pos]){
if(x == prev) continue;
ans -= sz[x] * sz[x];
}
}
else if(nadj[pos].size() >= 3){
int lft = tsz - sz[pos], mid = nadj[pos].size() - 2;
ans += tsz * tsz * mid;
ans -= lft * lft * mid;
for(auto x : nadj[pos]){
if(x == prev) continue;
ans -= sz[x] * sz[x] * mid;
}
}
for(auto x : nadj[pos]){
if(x == prev) continue;
dfs3(x, pos, tsz);
}
}
signed main(void){
fastio;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
a--, b--;
adj[a].pb(b);
adj[b].pb(a);
}
for(int i = 0; i < n; i++){
if(!in[i]){
dfs(i);
dfs2(i, -1);
dfs3(i, -1, sz[i]);
}
}
cout<<ans<<"\n";
}
Compilation message (stderr)
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:33:21: warning: unused variable 'sz' [-Wunused-variable]
33 | int sz = nadj[cur].size();
| ^~
# | 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... |