#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 300000 + 10;
const int INF = 1e9;
int n, m;
int compCnt;
int inComp[MAXN];
int compSZ[MAXN];
bool addedEdge[MAXN];
std::vector <int> g[MAXN];
std::vector <int> rev[MAXN];
std::vector <int> inSCC[MAXN];
std::vector <int> dag[MAXN];
std::stack <int> topSort;
bool vis[MAXN];
int from[MAXM];
int to[MAXM];
void topSortDFS(int node)
{
vis[node] = true;
for (const int &u : g[node])
{
if (!vis[u])
{
topSortDFS(u);
}
}
topSort.push(node);
}
void sccDFS(int node)
{
vis[node] = true;
inComp[node] = compCnt;
inSCC[compCnt].push_back(node);
compSZ[compCnt]++;
for (const int &u : rev[node])
{
if (vis[u]) continue;
sccDFS(u);
}
}
llong solveDFS(int node)
{
vis[node] = true;
llong res = (1LL * compSZ[node] * (compSZ[node] - 1));
for (const int &u : dag[node])
{
if (!vis[u])
{
res += solveDFS(u);
}
res += compSZ[u];
}
return res;
}
llong calcANS()
{
compCnt = 0;
std::fill(vis + 1, vis + 1 + n, false);
std::fill(inComp + 1, inComp + 1 + n, 0);
std::fill(compSZ + 1, compSZ + 1 + n, 0);
for (int i = 1 ; i <= n ; ++i)
{
inSCC[i].clear();
dag[i].clear();
}
for (int i = 1 ; i <= n ; ++i)
{
if (!vis[i])
{
topSortDFS(i);
tops.push_back(topSort.top());
}
}
std::fill(vis + 1, vis + 1 + n, false);
while (!topSort.empty())
{
int node = topSort.top();
topSort.pop();
if (!vis[node])
{
compCnt++;
sccDFS(node);
}
}
for (int i = 1 ; i <= compCnt ; ++i)
{
for (const int &node : inSCC[i])
{
addedEdge[i] = true;
for (const int &u : g[node])
{
if (addedEdge[inComp[u]]) continue;
dag[i].push_back(inComp[u]);
addedEdge[inComp[u]] = true;
}
for (const int &u : g[node])
{
addedEdge[inComp[u]] = false;
}
addedEdge[i] = false;
}
}
std::fill(vis + 1, vis + 1 + n, false);
std::reverse(tops.begin(), tops.end());
llong ans = 0;
for (const int &node : tops)
{
if (!vis[node])
{
ans += solveDFS(inComp[node]);
}
}
return ans;
}
void solve()
{
for (int i = 1 ; i <= m ; ++i)
{
g[from[i]].push_back(to[i]);
rev[to[i]].push_back(from[i]);
std::cout << calcANS() << '\n';
}
}
void input()
{
std::cin >> n >> m;
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> from[i] >> to[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
joitter2.cpp: In function 'llong calcANS()':
joitter2.cpp:90:13: error: 'tops' was not declared in this scope; did you mean 'to'?
90 | tops.push_back(topSort.top());
| ^~~~
| to
joitter2.cpp:129:18: error: 'tops' was not declared in this scope; did you mean 'to'?
129 | std::reverse(tops.begin(), tops.end());
| ^~~~
| to
