/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int N, M;
int root[N_MAX + 2];
int cnt[N_MAX + 2];
set <int> in[N_MAX + 2];
set <int> ins[N_MAX + 2];
set <pair <int, int>> out[N_MAX + 2];
int answer;
int f (int u) {
return (int) in[u].size() * cnt[u] + cnt[u] * (cnt[u] - 1);
}
int find_root (int u) {
return (root[u] == 0 ? u : root[u] = find_root(root[u]));
}
vector <pair <int, int>> join_que;
void del_edge (int u, int v) {
int ru = find_root(u), rv = find_root(v);
in[rv].erase(u);
out[u].erase({u, rv});
}
bool add_edge (int u, int v) {
int ru = find_root(u), rv = find_root(v);
if (ru == rv || ins[rv].find(ru) != ins[rv].end()) {
return false;
}
in[rv].insert(u);
out[ru].insert({u, rv});
ins[rv].insert(ru);
if (ins[ru].find(rv) != ins[ru].end()) {
join_que.push_back({ru, rv});
}
return true;
}
void join (int u, int v) {
if (u == v) {
return;
}
if ((int) in[u].size() + (int) out[u].size()
> (int) in[v].size() + (int) out[v].size()) {
swap(u, v);
}
answer -= f(u) + f(v);
vector <pair <int, int>> del, add;
for (int x : in[u]) {
del.push_back({x, u});
if (x != v) {
add.push_back({x, v});
}
}
for (pair <int, int> e : out[u]) {
del.push_back(e);
if (e.second != v) {
add.push_back(e);
}
}
for (pair <int, int> e : del) {
del_edge(e.first, e.second);
}
root[u] = v;
cnt[v] += cnt[u];
for (pair <int, int> e : add) {
add_edge(e.first, e.second);
}
answer += f(v);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
fill(cnt + 1, cnt + N + 1, 1);
while (M--) {
int u, v;
cin >> u >> v;
if (add_edge(u, v) == true) {
answer += cnt[find_root(v)];
while (join_que.empty() == false) {
pair <int, int> e = join_que.back();
join_que.pop_back();
join(e.first, e.second);
}
}
cout << answer << "\n";
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void del_edge(int, int)':
joitter2.cpp:37:9: warning: unused variable 'ru' [-Wunused-variable]
37 | int ru = find_root(u), rv = find_root(v);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
