#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
struct graph{
using Weight_t = T;
struct Edge_t{
int from, to;
T cost;
};
int n;
vector<Edge_t> edge;
vector<vector<int>> adj;
function<bool(int)> ignore;
graph(int n = 1): n(n), adj(n){
assert(n >= 1);
}
graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
}
else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
}
graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
}
else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
}
graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
}
graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
}
int operator()(int u, int id) const{
#ifdef LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int id = (int)edge.size();
adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
return id;
}
int orient(int u, int v, T w = {}){ // insert a directed edge
int id = (int)edge.size();
adj[u].push_back(id), edge.push_back({u, v, w});
return id;
}
void clear(){
for(auto [u, v, w]: edge){
adj[u].clear();
adj[v].clear();
}
edge.clear();
ignore = {};
}
graph transpose() const{ // the transpose of the directed graph
graph res(n);
for(auto id = 0; id < (int)edge.size(); ++ id){
if(ignore && ignore(id)) continue;
res.orient(edge[id].to, edge[id].from, edge[id].cost);
}
return res;
}
int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
return (int)adj[u].size();
}
// The adjacency list is sorted for each vertex.
vector<vector<int>> get_adjacency_list() const{
vector<vector<int>> res(n);
for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
if(ignore && ignore(id)) continue;
res[(*this)(u, id)].push_back(u);
}
return res;
}
void set_ignoration_rule(const function<bool(int)> &f){
ignore = f;
}
void reset_ignoration_rule(){
ignore = nullptr;
}
friend ostream &operator<<(ostream &out, const graph &g){
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
}
return out;
}
};
// Requires graph
struct biconnected_components{
int n, attempt, comp_attempt;
vector<int> pos;
vector<int> stack;
vector<int> was;
vector<int> comp_was;
// block-cut tree descriptions
vector<vector<int>> belongs; // vertex -> list of 2-vertex-connected components
vector<vector<int>> comp_vertex; // list of vertices in a 2-vertex-connected component
vector<vector<int>> comp_edge; // list of edges in a 2-vertex-connected component
vector<int> bridge;
biconnected_components(){ }
biconnected_components(int n){ init(n); }
template<class T>
biconnected_components(const graph<T> &g){ init(g.n); run_all(g); }
void init(int n){
this->n = n;
pos.assign(n, -1);
was.assign(n, -2);
attempt = -1;
comp_was.assign(n, -2);
comp_attempt = -1;
belongs.assign(n, {});
comp_vertex.clear();
comp_edge.clear();
bridge.clear();
}
// O(n + m) where n and m are the number of reachable nodes and edges respectively.
template<class T>
void _run(const graph<T> &g, const vector<int> &src){
int it = 0;
auto recurse = [&](auto self, int u, int pe)->int{
int low = pos[u] = ++ it;
belongs[u].clear();
was[u] = attempt;
for(auto id: g.adj[u]){
if(g.ignore && g.ignore(id) || id == pe) continue;
int v = g(u, id);
if(was[v] != attempt){
was[v] = attempt;
pos[v] = 0;
}
if(pos[v]){
low = min(low, pos[v]);
if(pos[v] < pos[u]) stack.push_back(id);
}
else{
int size = (int)stack.size(), up = self(self, v, id);
low = min(low, up);
if(up == pos[u]){
++ comp_attempt;
stack.push_back(id);
vector<int> comp_v;
vector<int> comp_e(stack.begin() + size, stack.end());
for(auto id: comp_e){
auto [u, v, _] = g.edge[id];
if(comp_was[u] != comp_attempt){
comp_was[u] = comp_attempt;
comp_v.push_back(u);
}
if(comp_was[v] != comp_attempt){
comp_was[v] = comp_attempt;
comp_v.push_back(v);
}
}
for(auto u: comp_v) belongs[u].push_back((int)comp_vertex.size());
comp_vertex.push_back(move(comp_v));
comp_edge.push_back(move(comp_e));
stack.resize(size);
}
else if(up < pos[u]) stack.push_back(id);
else{
belongs[g.edge[id].from].push_back((int)comp_vertex.size());
belongs[g.edge[id].to].push_back((int)comp_vertex.size());
comp_vertex.push_back({g.edge[id].from, g.edge[id].to});
comp_edge.push_back({id});
bridge.push_back(id);
}
}
}
return low;
};
for(auto u: src) if(was[u] != attempt) recurse(recurse, u, -1);
}
template<class T>
void run(const graph<T> &g, const vector<int> &src){
assert(g.n <= n);
for(auto u: src) assert(0 <= u && u < g.n);
comp_vertex.clear();
comp_edge.clear();
bridge.clear();
++ attempt;
_run(g, src);
}
template<class T>
void run_all(const graph<T> &g){
assert(g.n <= n);
comp_vertex.clear();
comp_edge.clear();
bridge.clear();
++ attempt;
vector<int> src(g.n);
iota(src.begin(), src.end(), 0);
_run(g, src);
}
// Check if u is visited during the last run-like call.
bool visited(int u) const{
assert(0 <= u && u < n);
return was[u] == attempt;
}
bool is_articulation_point(int u) const{
assert(0 <= u && u < n && visited(n));
return (int)belongs[u].size() >= 2;
}
bool is_bridge_component(int i) const{
assert(0 <= i && i < (int)comp_vertex.size());
return (int)comp_edge[i].size() == 1;
}
// # of 2-vertex-connected components
int count() const{
return (int)comp_vertex.size();
}
};
int n, visited[300300];
ll ans, dp0[300300], dp[300300];
vector<int> adj[300300];
int dfs1(int s, int pa = -1){
visited[s] = 1;
if (s < n) dp[s] = 1;
for (auto &v:adj[s]) if (v!=pa){
dp[s] += dfs1(v, s) - 1;
}
return dp[s];
}
void dfs2(int s, int pa = -1){
for (auto &v:adj[s]) if (v!=pa) dfs2(v, s);
if (s < n){
ll rem = n - 1;
for (auto &v:adj[s]) if (v!=pa){
ans -= (dp[v]-1) * (dp[v]-2);
rem -= dp[v]-1;
}
ans -= rem * (rem-1);
}
else{
ll rem = n - dp0[s];
for (auto &v:adj[s]) if (v!=pa){
ans -= (dp0[s]-(int)adj[s].size()) * dp[v] * (dp[v]-1);
rem -= dp[v]-1;
}
rem++;
ans -= (dp0[s]-(int)adj[s].size()) * rem * (rem-1);
}
}
int main(){
int m;
scanf("%d %d", &n, &m);
vector<array<int, 2>> E;
for (int i=0;i<m;i++){
int x, y;
scanf("%d %d", &x, &y);
--x, --y;
E.push_back({x, y});
}
graph<int> G(n, E);
biconnected_components BCC(G);
int sz = n + BCC.count();
for (int i=0;i<n;i++){
for (auto &x:BCC.belongs[i]){
assert(n+x < sz);
adj[i].push_back(n+x);
adj[n+x].push_back(i);
}
}
for (int i=0;i<sz;i++){
if (i<n) dp0[i] = dp[i] = 1;
else dp0[i] = dp[i] = BCC.comp_vertex[i-n].size();
}
for (int i=0;i<sz;i++) if (!visited[i]){
ll v = dfs1(i);
if (v <= 2) continue;
ans += v * (v-1) * (v-2);
dfs2(i);
}
printf("%lld\n", ans);
}
Compilation message
count_triplets.cpp: In instantiation of 'biconnected_components::_run<int>::<lambda(auto:23, int, int)> [with auto:23 = biconnected_components::_run<int>::<lambda(auto:23, int, int)>]':
count_triplets.cpp:186:42: required from 'void biconnected_components::_run(const graph<T>&, const std::vector<int>&) [with T = int]'
count_triplets.cpp:207:7: required from 'void biconnected_components::run_all(const graph<T>&) [with T = int]'
count_triplets.cpp:118:63: required from 'biconnected_components::biconnected_components(const graph<T>&) [with T = int]'
count_triplets.cpp:283:30: required from here
count_triplets.cpp:140:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
140 | if(g.ignore && g.ignore(id) || id == pe) continue;
| ~~~~~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:271:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
271 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:277:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
277 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
54976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
11208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 4 |
Correct |
3 ms |
11360 KB |
Output is correct |
| 5 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 6 |
Correct |
3 ms |
11096 KB |
Output is correct |
| 7 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 8 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 9 |
Correct |
3 ms |
11268 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
45128 KB |
Output is correct |
| 2 |
Correct |
138 ms |
44984 KB |
Output is correct |
| 3 |
Correct |
120 ms |
44992 KB |
Output is correct |
| 4 |
Correct |
129 ms |
45612 KB |
Output is correct |
| 5 |
Correct |
124 ms |
44772 KB |
Output is correct |
| 6 |
Correct |
165 ms |
58980 KB |
Output is correct |
| 7 |
Correct |
153 ms |
53836 KB |
Output is correct |
| 8 |
Correct |
136 ms |
51388 KB |
Output is correct |
| 9 |
Correct |
131 ms |
49324 KB |
Output is correct |
| 10 |
Incorrect |
121 ms |
44976 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11100 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
45384 KB |
Output is correct |
| 2 |
Correct |
135 ms |
44956 KB |
Output is correct |
| 3 |
Incorrect |
124 ms |
42932 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
