#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , M = 3e5 + 10;
int n , m;
long long fin_ans = 0;
struct DSU{
set <int> st[N];
int sz[N] , par[N];
void Build()
{
for(int i = 1 ; i <= n ; i++)
{
sz[i] = 1;
st[i].insert(i);
}
}
int root(int v)
{
return (par[v] == 0 ? v : par[v] = root(par[v]));
}
void Merge(int a , int b)
{
fin_ans -= 1LL * sz[a] * ((long long)st[a].size() - 1);
fin_ans -= 1LL * sz[b] * ((long long)st[b].size() - 1);
if(sz[a] > sz[b])
swap(a , b);
for(auto u : st[a])
st[b].insert(u);
st[a].clear();
par[a] = b;
sz[b] += sz[a];
fin_ans += 1LL * sz[b] * ((long long)st[b].size() - 1);
}
void Add(int a , int b)
{
int ra = root(a) , rb = root(b);
if(st[ra].find(b) != st[ra].end())
return;
if(st[rb].find(a) != st[rb].end())
{
Merge(ra , rb);
return;
}
st[ra].insert(b);
fin_ans += sz[ra];
}
} dsu;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
dsu.Build();
while(m--)
{
int u , v; cin >> u >> v;
dsu.Add(v , u);
cout << fin_ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
