#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 3e5 + 5, N = 1e6;
const ll oo = 1e18 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
int sz[nmax];
set<int> in[nmax], out[nmax];
int r[nmax];
int get(int u){
return r[u] ? r[u] = get(r[u]) : u;
}
ll ans = 0;
void Union(int u, int v){
int x = get(u);
int y = get(v);
if(x != y){
if(in[x].size() + out[x].size() > in[y].size() + out[y].size()) swap(x, y);
r[x] = y;
int it = (int) in[x].size();
ans -= (sz[x]) * it;
ans -= sz[x] * (sz[x] - 1);
it = (int)in[y].size();
ans -= (sz[y]) * it;
ans -= sz[y] * (sz[y] - 1);
vector<int> lis;
for(auto p : in[x]){
if(out[y].count(p)) lis.push_back(p);
out[p].erase(x);
out[p].insert(y);
in[y].insert(p);
}
for(auto p : out[x]){
if(in[y].count(p)) lis.push_back(p);
in[p].erase(x);
out[y].insert(p);
in[p].insert(y);
}
sz[y] += sz[x];
it = (int)in[y].size();
ans += (sz[y]) * it;
ans += sz[y] * (sz[y] - 1);
for(auto p : lis) Union(u, p);
}
}
bool check(int u, int v){
int x = get(u);
int y = get(v);
return out[x].count(y) > 0;
}
pii a[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
a[i] = {u, v};
}
for(int i = 1; i <= n; ++i) sz[i] = 1;
for(int i = 1; i <= m; ++i){
int u = a[i].fi, v = a[i].se;
if(get(u) == get(v)) continue;
u = get(u); v = get(v);
if(check(v, u)){
out[v].erase(u);
in[u].erase(v);
--ans;
Union(u, v);
}
else{
ans -= sz[v] * ((int)in[v].size());
out[u].insert(v);
in[v].insert(u);
ans += sz[v] * ((int)in[v].size());
}
cout <<ans << endl;
}
}
/*
*/
Compilation message
joitter2.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
62 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
