#include <bits/stdc++.h>
using namespace std;
#define int int64_t
signed main() {
int n,m;cin>>n>>m;
vector<vector<int>> g(n);
for (int i=0;i<m;i++) {
int a,b;cin>>a>>b;a--;b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<vector<int>> cmp;
stack<int> st;
vector<int> low(n, 1e9), num(n, 1e9);
vector<bool> isart(n, false);
int timer=0;
function<void(int,int)> dfs=[&](int node, int pv) {
low[node] = num[node] = timer++;
st.push(node);
for (int x:g[node]) {
if (x == pv) {
continue;
}
if (num[x] == (int)1e9) {
dfs(x, node);
low[node] = min(low[node], low[x]);
if (low[x] >= num[node]) {
isart[node] = true;
cmp.push_back({});
while (st.top() != node) {
cmp[cmp.size()-1].push_back(st.top());
st.pop();
}
cmp[cmp.size()-1].push_back(node);
}
}
else {
low[node] = min(low[node], num[x]);
}
}
};
for (int i=0;i<n;i++) {
if (num[i] == (int)1e9)dfs(i, -1);
}
int nn = n + cmp.size();
vector<vector<int>> ng(nn);
for (int i=0;i<cmp.size();i++) {
for (int x:cmp[i]) {
ng[x].push_back(i+n);
ng[i+n].push_back(x);
}
}
vector<bool> vis(nn, false);
vector<int> sz(nn, -1);
function<int(int)> dfs2=[&](int node) -> int {
vis[node] = true;
int ans = 0;
if (node < n) ans++;
for (int x:ng[node]) {
if (!vis[x]) ans += dfs2(x);
}
return ans;
};
for (int i=0;i<nn;i++) {
if (!vis[i]) {
sz[i] = dfs2(i);
}
}
vis.assign(n, false);
int tmpAns = 0, ans = 0;
function<int(int, int)> dfs3=[&](int node, int pv)-> int {
int sms = 0, smsSquare = 0;
for (int x:ng[node]) {
if (x == pv)continue;
int res = dfs3(x, node);
sms += res;
smsSquare += res * (res - 1);
}
if (node < n && isart[node]) {
ans -= smsSquare;
ans -= (tmpAns - sms) * (tmpAns - sms - 1);
}
return sms + (node < n);
};
for (int i=0;i<nn;i++) {
if (sz[i] == -1) continue;
tmpAns = sz[i];
ans += tmpAns * (tmpAns - 1) * (tmpAns - 2);
dfs3(i, -1);
}
cout<<ans<<"\n";
}
Compilation message
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i=0;i<cmp.size();i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
29120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
28420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
27928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
