#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 300000 + 10;
const int MOD = 1e9 + 7;
int n, m;
llong answer;
struct DSU
{
int sz[MAXN];
int par[MAXN];
std::map <int,int> fromComp[MAXN];
std::set <int> pointingNodes[MAXN];
std::set <int> fromNode[MAXN];
std::set <int> nodes[MAXN];
void build()
{
std::fill(sz + 1, sz + 1 + n, 1);
std::iota(par + 1, par + 1 + n, 1);
for (int i = 1 ; i <= n ; ++i)
{
nodes[i].insert(i);
}
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void merge(int cU, int cV)
{
cU = find(cU);
cV = find(cV);
if (cU == cV)
{
return;
}
answer -= 1LL * fromComp[cV][cU] * nodes[cU].size();
answer -= 1LL * fromComp[cU][cV] * nodes[cV].size();
answer += 2LL * nodes[cU].size() * nodes[cV].size();
if (nodes[cV].size() > nodes[cU].size())
{
std::swap(cV, cU);
}
std::queue <int> waitlist;
for (const int &node : pointingNodes[cV])
{
if (nodes[cU].count(node))
{
waitlist.push(node);
}
}
for (const int &node : nodes[cV])
{
if (fromNode[node].count(cU))
{
pointingNodes[cU].erase(pointingNodes[cU].find(node));
fromNode[node].erase(fromNode[node].find(cU));
}
}
fromComp[cU][cV] = 0;
fromComp[cV][cU] = 0;
while (waitlist.size())
{
pointingNodes[cV].erase(pointingNodes[cV].find(waitlist.front()));
waitlist.pop();
}
std::queue <std::pair <int,int>> toMerge;
for (const int &node : pointingNodes[cV])
{
if (fromNode[node].count(cU))
{
toMerge.push({cU, find(node)});
}
}
for (const auto &[key, value] : fromComp[cV])
{
if (value > 0 && fromComp[key][cU] > 0)
{
toMerge.push({cU, key});
}
}
answer -= 1LL * nodes[cV].size() * pointingNodes[cV].size();
for (const int &node : pointingNodes[cV])
{
fromNode[node].erase(fromNode[node].find(cV));
fromComp[find(node)][cV]--;
bool inserted = pointingNodes[cU].insert(node).second;
if (inserted)
{
answer += nodes[cU].size();
fromNode[node].insert(cU);
fromComp[find(node)][cU]++;
}
}
answer += 1LL * pointingNodes[cU].size() * nodes[cV].size();
for (const auto &[key, value] : fromComp[cV])
{
fromComp[cU][key] += value;
}
for (const int &node : nodes[cV])
{
nodes[cU].insert(node);
}
par[cV] = cU;
while (toMerge.size())
{
merge(toMerge.front().first, toMerge.front().second);
toMerge.pop();
}
}
void addEdge(int u, int v)
{
int cU = find(u);
int cV = find(v);
if (cU == cV)
{
return;
}
if (fromNode[u].count(cV))
{
return;
}
if (!fromComp[cV].count(cU))
{
answer += nodes[cV].size();
pointingNodes[cV].insert(u);
fromNode[u].insert(cV);
fromComp[cU][cV]++;
return;
}
assert(fromComp[cU][cV] == 0);
merge(cU, cV);
}
};
DSU dsu;
int from[MAXM];
int to[MAXM];
void solve()
{
dsu.build();
for (int i = 1 ; i <= m ; ++i)
{
dsu.addEdge(from[i], to[i]);
std::cout << answer << '\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;
}
/*
14 13
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4
5 6
4 2
1 5
2 3
2 5
3 2
3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
22104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
22104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
22104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
