#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n,m,a[MAXN],b[MAXN],k;
int dp[MAXN],low[MAXN];
vector< pair<int,int> > v[MAXN];
vector<int> g[MAXN];
stack<int> st;
int li[MAXN],tim,sz[MAXN];
long long ans;
void bcc(int x,int p,int dep){
st.push(x);
li[x]=tim; dp[x]=low[x]=dep;
int ch=0;
for(int i=0;i<v[x].size();i++){
if(li[v[x][i].first]!=tim){
bcc(v[x][i].first,x,dep+1); ch++;
low[x]=min(low[x],low[v[x][i].first]);
if(low[v[x][i].first]>=dp[x]){
k++;
g[k].push_back(x);
g[x].push_back(k);
cout<<k<<" "<<x<<"\n";
while(!st.empty()){
cout<<st.top()<<" "<<k<<"\n";
g[st.top()].push_back(k);
g[k].push_back(st.top());
if(st.top()==v[x][i].first){
st.pop(); break;
}
st.pop();
}
}
}else if(v[x][i].first!=p){
low[x]=min(low[x],dp[v[x][i].first]);
}
}
}
void dfs(int x,int p){
sz[x]=(x<=n);
for(int i=0;i<g[x].size();i++){
if(g[x][i]==p)continue;
dfs(g[x][i],x);
sz[x]+=sz[g[x][i]];
}
}
void dfs2(int x,int p,int szcomp){
for(int i=0;i<g[x].size();i++){
if(g[x][i]==p)continue;
dfs2(g[x][i],x,szcomp);
if(x>n)ans-=(long long) (g[x].size()-1) * (sz[g[x][i]]-1) * (sz[g[x][i]]);
}
if(x>n)ans-=(long long) (g[x].size()-1) * (szcomp-sz[x]-1) * (szcomp-sz[x]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
v[a[i]].push_back({b[i],i});
v[b[i]].push_back({a[i],i});
}
tim++; k=n;
for(int i=1;i<=n;i++){
if(li[i]!=tim)bcc(i,0,0);
}
tim++;
for(int i=1;i<=k;i++){
if(sz[i]!=0)continue;
dfs(i,0);
ans+=(long long) sz[i]*(sz[i]-1)*(sz[i]-2);
dfs2(i,0,sz[i]);
}
cout<<ans<<"\n";
return 0;
}
Compilation message
count_triplets.cpp: In function 'void bcc(int, int, int)':
count_triplets.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<g[x].size();i++){
| ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, int)':
count_triplets.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i=0;i<g[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
30668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
26436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
26436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
