#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18;
const ll INF = 1e15;
const ll MAXN = 1e5 + 5;
vector<set<int>> graph, rev;
queue<pair<int,int>> q;
set<int> in[MAXN];
int par[MAXN];
ll sz[MAXN];
ll ans = 0;
int find(int node) {
if (par[node] == node)
return node;
return par[node] = find(par[node]);
}
void conn(int from, int to) {
graph[from].insert(to);
rev[to].insert(from);
if (graph[to].count(from))
q.push({from, to});
}
void merge(int x, int y) {
if (x == y)
return ;
bool swapped = false;
if (graph[x].size() + rev[x].size() + in[x].size() < graph[y].size() + rev[y].size() + in[y].size()) {
swap(x, y);
swapped = true;
}
ans += in[y].size() * sz[x] + in[x].size() * sz[y];
sz[x] += sz[y];
par[y] = x;
if (swapped)
swap(x, y);
for (auto u : in[y]) {
if (in[x].count(u) == 0)
in[x].insert(u);
else
ans -= sz[x];
}
graph[x].erase(y);
graph[y].erase(x);
rev[x].erase(y);
rev[y].erase(x);
for (auto u : graph[y]) {
rev[u].erase(y);
conn(x, u);
}
for (auto u : rev[y]) {
graph[u].erase(y);
conn(u, x);
}
}
int main() {
fast
int N, M, a, b;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
par[i] = i, sz[i] = 1;
in[i].insert(i);
}
graph = vector<set<int>>(N+1, set<int>());
rev = vector<set<int>>(N+1, set<int>());
for (int i = 1; i <= M; i++) {
cin >> a >> b;
int par_a = find(a);
int par_b = find(b);
if (par_b == par_a)
continue;
if (in[par_b].count(a) == 0) {
in[par_b].insert(a);
ans += sz[par_b];
conn(par_a, par_b);
while (!q.empty()) {
int from = q.front().f;
int to = q.front().s;
q.pop();
merge(find(from), find(to));
}
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
