#include <bits/stdc++.h>
using namespace std;
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector< vector<int> > g;
int n;
function<bool(int)> ignore;
graph(int _n) : n(_n) {
g.resize(n);
ignore = nullptr;
}
virtual int add(int from, int to, T cost) = 0;
virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
ignore = f;
}
virtual void reset_ignore_edge_rule() {
ignore = nullptr;
}
};
template <typename T>
class undigraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
undigraph(int _n) : graph<T>(_n) {
}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_undigraph : public undigraph<T> {
public:
using undigraph<T>::edges;
using undigraph<T>::g;
using undigraph<T>::n;
using undigraph<T>::ignore;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<int> min_depth;
vector<T> dist;
vector<int> was;
int attempt;
dfs_undigraph(int _n) : undigraph<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
min_depth = vector<int>(n, -1);
dist = vector<T>(n);
was = vector<int>(n, -1);
attempt = 0;
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
min_depth.clear();
dist.clear();
was.clear();
}
private:
void do_dfs(int v) {
was[v] = attempt;
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
min_depth[v] = depth[v];
for (int id : g[v]) {
if (id == pe[v] || (ignore != nullptr && ignore(id))) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
if (was[to] == attempt) {
min_depth[v] = min(min_depth[v], depth[to]);
continue;
}
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
min_depth[v] = min(min_depth[v], min_depth[to]);
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
++attempt;
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
template <typename T>
vector<int> find_bicone(dfs_undigraph<T> &g, int &cnt) {
g.dfs_all();
vector<int> vertex_comp(g.n);
cnt = 0;
for (int i : g.order) {
if (g.pv[i] == -1 || g.min_depth[i] == g.depth[i]) {
vertex_comp[i] = cnt++;
} else {
vertex_comp[i] = vertex_comp[g.pv[i]];
}
}
return vertex_comp;
}
struct dsu {
int nCC;
vector<int> pr, sz, rank;
dsu(int n) {
nCC = n;
pr.resize(n);
sz.assign(n, 1);
rank.assign(n, 1);
iota(pr.begin(), pr.end(), 0);
}
int fnd(int u) {
if (u == pr[u]) {
return u;
}
pr[u] = fnd(pr[u]);
return pr[u];
}
bool unate(int u, int v) {
u = fnd(u); v = fnd(v);
if (u == v) {
return false;
}
--nCC;
if (rank[u] > rank[v]) {
swap(u, v);
}
pr[u] = v;
rank[v] += (rank[u] == rank[v]);
sz[v] += sz[u];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long n, m;
cin >> n >> m;
dfs_undigraph<long long> gg(n);
dsu se(n);
for (long long i = 0; i < m; i++) {
long long u, v;
cin >> u >> v;
--u; --v;
gg.add(u, v);
se.unate(u, v);
}
long long cnt;
vector<long long> comp = find_bicone(gg, cnt);
vector<long long> a(cnt, 0);
vector<long long> dsu_par(cnt);
for (long long i = 0; i < n; i++) {
a[comp[i]]++;
dsu_par[comp[i]] = i;
}
dsu se2(n);
for (long long i = 0; i < n; i++) {
se2.unate(i, dsu_par[comp[i]]);
}
vector<vector<long long>> g(cnt);
vector<long long> deg(cnt, 0);
for (auto e : gg.edges) {
if (se2.unate(e.from, e.to)) {
g[comp[e.from]].push_back(comp[e.to]);
g[comp[e.to]].push_back(comp[e.from]);
deg[comp[e.from]]++;
deg[comp[e.to]]++;
}
}
long long ans = 0;
for (long long i = 0; i < cnt; i++) {
dsu_par[i] = se.fnd(dsu_par[i]);
if (a[i] > 2) {
ans += a[i] * 1LL * (a[i] - 1) * (a[i] - 2);
}
if (a[i] > 1) {
ans += (a[i] - deg[i]) * 2LL * (a[i] - 1) * (se.sz[dsu_par[i]] - a[i]);
}
}
vector<long long> sbt(cnt, 0);
function<long long(long long, long long)> dfs0 = [&](long long u, long long p) {
long long r = 1;
sbt[u] = a[u];
for (long long v : g[u]) {
if (v != p) {
r += dfs0(v, u);
sbt[u] += sbt[v];
}
}
return r;
};
function<void(long long, long long, long long)> DFS = [&](long long u, long long p, long long nn) {
for (long long v : g[u]) {
if (v != p) {
DFS(v, u, nn);
}
}
long long sum = nn - 1;
long long sbtp = nn - sbt[u];
ans += sbtp * 1LL * (sum - sbtp);
for (long long v : g[u]) {
if (v != p) {
ans += sbt[v] * 1LL * (sum - sbt[v]);
}
}
};
for (long long i = 0; i < cnt; i++) {
if (sbt[i] == 0) {
long long
sz = dfs0(i, -1);
if (sz > 2) {
DFS(i, -1, sz);
}
}
}
cout << ans << '\n';
return 0;
}
Compilation message
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:233:46: error: no matching function for call to 'find_bicone(dfs_undigraph<long long int>&, long long int&)'
233 | vector<long long> comp = find_bicone(gg, cnt);
| ^
count_triplets.cpp:171:13: note: candidate: 'template<class T> std::vector<int> find_bicone(dfs_undigraph<T>&, int&)'
171 | vector<int> find_bicone(dfs_undigraph<T> &g, int &cnt) {
| ^~~~~~~~~~~
count_triplets.cpp:171:13: note: template argument deduction/substitution failed:
count_triplets.cpp:233:43: note: cannot convert 'cnt' (type 'long long int') to type 'int&'
233 | vector<long long> comp = find_bicone(gg, cnt);
| ^~~
