#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int N, M, dsu[100005], rk[100005];
ll ans;
set<int> fd[100005], f[100005];
vector<pii> chain;
int find(int k)
{
return k == dsu[k] ? k : dsu[k] = find(dsu[k]);
}
void Merge(set<int> &small, set<int> &big)
{
for(int i : small)
big.insert(i);
}
void query(set<int> &small, set<int> &big, int another)
{
for(int i : small)
if(big.find(i) != big.end())
chain.emplace_back(pii(i, another));
}
void follow(int a, int b)
{
//cout << "merge " << a << " " << b << '\n';
// out A <-> in B
if(f[a].size() <= fd[b].size())
query(f[a], fd[b], a);
else query(fd[b], f[a], a);
if(f[b].size() <= fd[a].size())
query(f[b], fd[a], a);
else query(fd[a], f[b], a);
ll ag = fd[a].size(), bg = fd[b].size(), rep;
if(fd[a].size() <= fd[b].size())
Merge(fd[a], fd[b]);
else Merge(fd[b], fd[a]);
rep = ag + bg - max(fd[a].size(), fd[b].size());
if(f[a].size() <= f[b].size())
Merge(f[a], f[b]);
else Merge(f[b], f[a]);
ans += ag * rk[b] + bg * rk[a] - rep * (rk[a] + rk[b]);
//cout << "update ans " << ans << '\n';
if(rk[a] <= rk[b])
{
dsu[a] = b;
rk[b] += rk[a];
if(f[a].size() >= f[b].size())
f[a].swap(f[b]);
if(fd[a].size() >= fd[b].size())
f[b].swap(f[a]);
}
else
{
dsu[b] = a;
rk[a] += rk[b];
fd[a].swap(fd[b]);
if(f[a].size() <= f[b].size())
f[a].swap(f[b]);
if(fd[a].size() <= fd[b].size())
f[b].swap(f[a]);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M;
for(int i = 1; i <= N; i++)
{
dsu[i] = i, rk[i] = 1;
fd[i].insert(i);
f[i].insert(i);
}
for(int i = 1; i <= M; i++)
{
int A, B;
cin >> A >> B;
if(find(A) == find(B));
else if(fd[find(B)].find(A) != fd[find(B)].end());
else if(fd[find(A)].find(B) != fd[find(A)].end())
{
//cout << "mergeeee\n";
chain.emplace_back(pii(A, B));
}
else
{
//cout << "simple follow\n";
fd[find(B)].insert(A);
f[find(A)].insert(B);
ans += rk[find(B)];
if(f[find(B)].find(A) != f[find(B)].end())
chain.emplace_back(pii(A, B));
}
while(!chain.empty())
{
auto [a, b] = chain.back();
chain.pop_back();
if(find(a) != find(b))
follow(find(a), find(b));
}
cout << ans << '\n';
}
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:113:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | auto [a, b] = chain.back();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
