#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 2;
int n, m, uf[MAXN], sz[MAXN], cnt_inside[MAXN];
ll ans;
set<int> in[MAXN], out[MAXN];
unordered_map<int, bool> edge[MAXN];
int f(int x){
while(uf[x] != -1) x = uf[x];
return x;
}
void merge_set(set<int>& a, set<int>& b){
if(a.size() > b.size()) swap(a, b);
for(int x : a) b.insert(x);
}
void join(int u, int v){
ans += 2LL * sz[u] * sz[v];
ans -= (ll)sz[u] * (in[u].size() - cnt_inside[u]) + (ll)sz[v] * (in[v].size() - cnt_inside[v]);
if(out[u].size() + in[u].size() > out[v].size() + in[v].size()) swap(u, v);
int nxt = -1;
for(int x : out[u]){
if(edge[x][v] && f(x) != v) nxt = x;
}
for(int x : in[u]){
edge[x][v] = 1;
if(edge[v][x] && f(x) != v) nxt = x;
}
for(int x : out[u]){
if(f(x) == v) ++cnt_inside[v];
}
for(int x : in[u]){
if(f(x) == v) ++cnt_inside[v];
}
merge_set(out[u], out[v]);
merge_set(in[u], in[v]);
uf[u] = v;
sz[v] += sz[u];
cnt_inside[v] += cnt_inside[u];
ans += (ll)sz[v] * (in[v].size() - cnt_inside[v]);
if(nxt != -1) join(f(nxt), v);
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; ++i) uf[i] = -1, sz[i] = 1;
for(int i = 0; i < m; ++i){
int u, v; cin >> u >> v, --u, --v;
int fu = f(u), fv = f(v);
if(fu == fv){
++cnt_inside[fu];
in[fu].insert(fu);
out[fu].insert(fu);
continue;
}
bool exist = 0;
for(int x : out[fv]){
if(f(x) == fu) exist = 1;
}
if(exist){
join(fu, fv);
} else {
if(!edge[u][fv]){
edge[u][fv] = 1;
ans += sz[fv];
}
in[fv].insert(u);
out[fu].insert(v);
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
