#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 100010;
vector<int> edge[MAXN];
map<int, int> bcce[MAXN];
int bcc_cnt = 0;
int pre_cnt = 0;
int pre[MAXN];
int low[MAXN];
int mypar[MAXN];
int is_sep[MAXN];
long long sum_perm_cnt = 0;
long long node_cnt[MAXN];
long long p[MAXN * 2];
set<int> bcc_node[MAXN * 2];
stack<pair<int, int> > st;
long long ans = 0;
inline const long long nP3(long long n) {
return n * (n - 1) * (n - 2);
}
inline const long long nP2(long long n) {
return n * (n - 1);
}
void dfs(int u, int par) {
int child = 0, flag = 0;
mypar[u] = par;
node_cnt[u] = 1;
low[u] = pre[u] = ++pre_cnt;
for(auto &v: edge[u]) {
if(v == par) continue;
if(!pre[v]) {
child++;
st.push({u, v});
dfs(v, u);
node_cnt[u] += node_cnt[v];
low[u] = min(low[u], low[v]);
if(pre[u] <= low[v]) {
bcc_cnt++;
flag = 1;
while(st.size() && (st.top().first != u || st.top().second != v)) {
int x = st.top().first;
int y = st.top().second;
bcc_node[bcc_cnt].insert(x);
bcc_node[bcc_cnt].insert(y);
bcce[x][y] = bcc_cnt;
bcce[y][x] = bcc_cnt;
st.pop();
}
if(st.size()) {
int x = st.top().first;
int y = st.top().second;
bcc_node[bcc_cnt].insert(x);
bcc_node[bcc_cnt].insert(y);
bcce[x][y] = bcc_cnt;
bcce[y][x] = bcc_cnt;
st.pop();
}
ans += nP3(bcc_node[bcc_cnt].size());
p[bcc_cnt] = nP2(bcc_node[bcc_cnt].size() - 1);
}
}
else if(pre[u] > pre[v]) {
st.push({u, v});
low[u] = min(low[u], pre[v]);
}
}
if(child >= 2 && par == -1) is_sep[u] = 1;
else if(flag && par != -1) is_sep[u] = 1;
}
int chk[MAXN];
void solve(int u, int par) {
long long sum_node_cnt = node_cnt[1] - node_cnt[u];
chk[u] = 1;
long long sep = is_sep[u];
for (auto &v: edge[u]) {
if(chk[v]) continue;
solve(v, u);
ans += sep * sum_node_cnt * node_cnt[v] * 2;
sum_node_cnt += node_cnt[v];
}
if(!sep) {
return;
}
for(auto &v: edge[u]) {
if(par != v && mypar[v] != u) continue;
int bcc = bcce[u][v];
if(par != v) {
ans += (node_cnt[1] - node_cnt[v] - 1) * p[bcc] * 2;
}
else {
ans += (node_cnt[1] - node_cnt[u]) * p[bcc] * 2;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1, 0);
solve(1, 0);
cout << ans << "\n";
return 0;
}
Compilation message
count_triplets.c:1:10: fatal error: algorithm: No such file or directory
1 | #include <algorithm>
| ^~~~~~~~~~~
compilation terminated.
