#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, m, u, v, nod, cnt = 0, sz[2 * N], sub[2 * N], num[N], low[N];
long long ans = 0;
bool vis[2 * N];
vector<int> st, com[N], adj[N], cut[2 * N];
vector<vector<int>> bi;
void process(vector<int> &ve)
{
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
++nod;
for (int &v : ve)
{
sz[nod]++;
com[v].push_back(nod);
}
}
void DFS(int u, int p = 0)
{
low[u] = num[u] = ++cnt;
for (int &v : adj[u])
if (v != p)
{
if (num[v] > 0)
low[u] = min(low[u], num[v]);
else
{
st.push_back(u);
DFS(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= num[u])
{
int v; bi.push_back({});
do
{
v = st.back(); st.pop_back();
bi.back().push_back(v);
} while (u != v);
process(bi.back());
}
}
}
st.push_back(u);
}
int get_subtree(int u, int p = 0)
{
sub[u] = sz[u];
for (int &v : cut[u])
if (v != p)
sub[u] += get_subtree(v, u);
return sub[u];
}
void find_ans(int u, int tot)
{
vis[u] = true;
int ver = com.size(), big = u > n;
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (tot - sz[u]);
int cur = tot - sub[u];
for (int &v : cut[u])
if (!vis[v])
{
find_ans(v, tot);
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
cur += sub[v];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
nod = n;
while (m--)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (num[i] == 0)
DFS(i);
for (int i = 1; i <= n; i++)
if (com[i].size() > 1)
{
sz[i] = 1;
for (int &v : com[i])
{
sz[v]--;
cut[i].push_back(v);
cut[v].push_back(i);
}
}
for (int i = 1; i <= nod; i++)
if (!vis[i])
find_ans(i, get_subtree(i));
for (int i = n + 1; i <= nod; i++)
{
int ver = cut[i].size();
ans += 1LL * ver * (sz[i] + ver - 1) * (sz[i] + ver - 2);
}
cout << ans;
}
st.push_back(u);
}
int get_subtree(int u, int p = 0)
{
sub[u] = sz[u];
for (int &v : cut[u])
if (v != p)
sub[u] += get_subtree(v, u);
return sub[u];
}
void find_ans(int u, int tot)
{
vis[u] = true;
int ver = com.size(), big = u > n;
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
int cur = tot - sub[u];
for (int &v : cut[u])
if (!vis[v])
{
find_ans(v, tot);
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
cur += sub[v];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
nod = n;
while (m--)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (num[i] == 0)
DFS(i);
for (int i = 1; i <= n; i++)
if (com[i].size() > 1)
{
sz[i] = 1;
for (int &v : com[i])
{
sz[v]--;
cut[i].push_back(v);
cut[v].push_back(i);
}
}
for (int i = 1; i <= nod; i++)
if (!vis[i])
find_ans(i, get_subtree(i));
for (int i = n + 1; i <= nod; i++)
{
int ver = cut[i].size();
ans += 1LL * ver * (sz[i] + ver - 1) * (sz[i] + ver - 2);
}
cout << ans;
}
Compilation message
count_triplets.cpp:130:2: error: stray '\302' in program
vis[u] = true;
^
count_triplets.cpp:130:3: error: stray '\240' in program
vis[u] = true;
^
count_triplets.cpp:130:5: error: stray '\302' in program
vis[u] = true;
^
count_triplets.cpp:130:6: error: stray '\240' in program
vis[u] = true;
^
count_triplets.cpp:131:2: error: stray '\302' in program
int ver = com.size(), big = u > n;
^
count_triplets.cpp:131:3: error: stray '\240' in program
int ver = com.size(), big = u > n;
^
count_triplets.cpp:131:5: error: stray '\302' in program
int ver = com.size(), big = u > n;
^
count_triplets.cpp:131:6: error: stray '\240' in program
int ver = com.size(), big = u > n;
^
count_triplets.cpp:132:2: error: stray '\302' in program
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^
count_triplets.cpp:132:3: error: stray '\240' in program
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^
count_triplets.cpp:132:5: error: stray '\302' in program
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^
count_triplets.cpp:132:6: error: stray '\240' in program
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^
count_triplets.cpp:133:2: error: stray '\302' in program
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
^
count_triplets.cpp:133:3: error: stray '\240' in program
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
^
count_triplets.cpp:133:5: error: stray '\302' in program
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
^
count_triplets.cpp:133:6: error: stray '\240' in program
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
^
count_triplets.cpp:139:2: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:3: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:5: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:6: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:8: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:9: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:11: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:12: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:14: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:15: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:17: error: stray '\302' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp:139:18: error: stray '\240' in program
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
^
count_triplets.cpp: In function 'void find_ans(int, int)':
count_triplets.cpp:67:19: error: request for member 'size' in 'com', which is of non-class type 'std::vector<int> [100005]'
int ver = com.size(), big = u > n;
^~~~
count_triplets.cpp:68:47: error: 'big' was not declared in this scope
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^~~
count_triplets.cpp:68:47: note: suggested alternative: 'bi'
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
^~~
bi
count_triplets.cpp: At global scope:
count_triplets.cpp:116:5: error: 'st' does not name a type
st.push_back(u);
^~
count_triplets.cpp:117:1: error: expected declaration before '}' token
}
^
