#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
//freopen(FOUT, "w", stdout);
fast_io();
}
const int MAX = 1e5 + 5;
vi adj[MAX];
vi comp[MAX];
vi bcomp[MAX];
ll precomp[MAX];
int get_sz[MAX];
int bad[MAX];
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash1 {
int operator()(int x) const { return hash<int>{}(x ^ RANDOM); }
};/*
gp_hash_table<int, int, chash1> vis;
gp_hash_table<int, int, chash1> sub;
gp_hash_table<int, int, chash1> parent;
*/
unordered_map<int, int> vis;
unordered_map<int, int> sub;
unordered_map<int, int> parent;
unordered_map<int, vi> tree1;
template<int SZ> struct DSU{
int par[SZ], sz[SZ];
DSU(){
for(int i = 0; i<SZ; i++){
par[i] = i;
sz[i] = 1;
}
}
int get(int x){
if(par[x] != x){
par[x] = get(par[x]);
}
return par[x];
}
bool unite(int x, int y){
x = get(x);
y = get(y);
if(x == y){
return false;
}
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
par[y] = x;
return true;
}
};
DSU<MAX> d;
int dfs(int src, int par){
assert(times<=1e6);
vis[src] = 1;
parent[src] = par;
sub[src] = sz(bcomp[src]);
if(src>=MAX){
sub[src] = sz(bcomp[src - MAX]) - bad[src-MAX];
}
else{
sub[src] = 1;
}
for(int nxt: tree1[src]){
if(nxt != par){
sub[src] += dfs(nxt, src);
}
}
return sub[src];
}
template<int SZ> struct BCC {
int N;
vi adj[SZ];
vector<vpi> fin;
void addEdge(int u, int v) { adj[u].pb(v), adj[v].pb(u); }
int ti = 0, disc[SZ], low[SZ], comp[SZ], par[SZ];
vpi st;
void BCCutil(int u, bool root = 0) {
disc[u] = low[u] = ti++;
int child = 0;
trav(i,adj[u]) if (i != par[u])
if (disc[i] == -1) {
child ++; par[i] = u;
st.pb({u,i});
BCCutil(i);
low[u] = min(low[u],low[i]);
// disc[u] < low[i]: bridge
if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
vpi tmp;
while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
tmp.pb(st.back()), st.pop_back();
fin.pb(tmp);
}
} else if (disc[i] < disc[u]) {
low[u] = min(low[u],disc[i]);
st.pb({u,i});
}
}
void bcc(int _N) {
N = _N;
f1r(i,1,N+1) par[i] = disc[i] = low[i] = -1;
f1r(i,1,N+1) if (disc[i] == -1) {
BCCutil(i,1);
if (sz(st)) fin.pb(st);
st.clear();
}
}
};
BCC<MAX> bcc;
int n;
int get(int above, int below){
if(parent[below] == above){
return sub[below];
}
else{
return get_sz[below] - sub[above];
}
}
int main(){
auto start = chrono::high_resolution_clock::now();
io("test");
//fast_io();
int m;
//cin >> n >> m;
scanf("%d %d", &n, &m);
f0r(i, m){
int u, v;
scanf("%d %d", &u, &v);
// cin >> u >> v;
u--;
v--;
d.unite(u, v);
adj[u].eb(v);
adj[v].eb(u);
bcc.addEdge(u+1, v+1);
}
f0r(i, n){
get_sz[i] = d.sz[d.get(i)];
}
bcc.bcc(n);
int sz = sz(bcc.fin);
f0r(i, sz){
for(auto e: bcc.fin[i]){
comp[e.f-1].eb(i);
comp[e.s-1].eb(i);
//bcomp[i].eb(e.f-1);
//bcomp[i].eb(e.s-1);
}
}
f0r(i, n){
set<int> s (all(comp[i]));
comp[i].assign(all(s));
for(auto x: comp[i]){
bcomp[x].eb(i);
}
}
/* f0r(i, sz){
set<int> s (all(bcomp[i]));
bcomp[i].assign(all(s));
}*/
f0r(i, n){
if(sz(comp[i]) == 1)continue;
for(int c: comp[i]){
tree1[i].eb(c+MAX);
tree1[c+MAX].eb(i);
}
}
f0r(i,sz){
for(int x: bcomp[i]){
if(sz(comp[x]) >1){
bad[i]++;
}
}
}
//dfs(MAX, -1);
/*auto end1 = chrono::high_resolution_clock::now();
// Calculating total time taken by the program.
double time_taken1 =
chrono::duration_cast<chrono::nanoseconds>(end1 - start).count();
time_taken1 *= 1e-9;
cout << "Time taken by program is : " << fixed
<< time_taken1 << setprecision(9);
cout << " sec" << endl;*/
f0r(i, sz){
if(vis.find(i + MAX) == vis.end()){
dfs(i+MAX, -1);
}
}
f0r(i, sz){
for(int x: bcomp[i]){
if(sz(comp[x]) > 1){
ll val = get(i+MAX, x);
precomp[i] += (val)*(val-1);
}
}
}
ll ans = 0;
f0r(i, n){
ll cur = get_sz[i] - 1;
if(sz(comp[i]) == 1){
///not a cut point
cur *=(cur-1);
int c = comp[i][0];
for(auto pnt: bcomp[c]){
if(sz(comp[pnt]) > 1){///cut point
ll val = get(c+MAX, pnt);
cur -= val*(val-1);
}
}
ans += cur;
}
else{
cur *= (cur-1);
for(int nxt: tree1[i]){
ll val = precomp[nxt-MAX];
ll subtract = get(nxt, i);
val -= subtract*(subtract - 1);
cur -= val;
}
ans += cur;
}
//cout << i << " " << cur << endl;
}
cout << ans << endl;
// cout << parent[1]- MAX << endl;
//cout << sub[3+MAX] << endl;
// cout << sub[5]<< endl;
/*auto end = chrono::high_resolution_clock::now();
// Calculating total time taken by the program.
double time_taken =
chrono::duration_cast<chrono::nanoseconds>(end - start).count();
time_taken *= 1e-9;
cout << "Time taken by program is : " << fixed
<< time_taken << setprecision(9);
cout << " sec" << endl;*/
return 0;
}
Compilation message
count_triplets.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:47:17: warning: unused variable 'FOUT' [-Wunused-variable]
const char* FOUT = fout.c_str();
^~~~
In file included from /usr/include/c++/7/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45:0,
from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
from count_triplets.cpp:9:
count_triplets.cpp: In function 'int dfs(int, int)':
count_triplets.cpp:101:12: error: 'times' was not declared in this scope
assert(times<=1e6);
^
count_triplets.cpp:101:12: note: suggested alternative: 'time'
count_triplets.cpp: In member function 'void BCC<SZ>::BCCutil(int, bool)':
count_triplets.cpp:132:27: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
trav(i,adj[u]) if (i != par[u])
^
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
