#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int maxn = 3e5+5;
const ll inf = 1e18;
int n, m;
ll ans = 0;
struct dsu{
int root = -1;
set<int> in;
set<int> out;
};
dsu up[maxn];
int Find(int x){
if(up[x].root < 0)return x;
else{
up[x].root = Find(up[x].root);
return up[x].root;
}
}
queue<pair<int, int>> edges;
void Union(int a, int b){
ans+=up[a].root;
up[a].in.erase(b);
up[b].out.erase(a);
if(up[a].in.size() + up[a].out.size() < up[b].in.size() + up[b].out.size())swap(a, b);
ans+=1LL*up[a].root*(-up[a].root-1);
ans+=1LL*up[b].root*(-up[b].root-1);
ans -= 1LL*up[b].root*up[a].in.size();
for(auto it = up[b].in.begin(); it != up[b].in.end(); it++){
ans+=up[b].root;
up[*it].out.erase(b);
edges.push({*it, a});
}
for(auto it = up[b].out.begin(); it != up[b].out.end(); it++){
ans+=up[*it].root;
up[*it].in.erase(b);
edges.push({a, *it});
}
up[a].root+=up[b].root;
up[b].root = a;
ans-=1LL*up[a].root*(-up[a].root-1);
//cout << a << " " << b << " " << ans << endl;
}
void add(int a, int b){
a = Find(a);
b = Find(b);
if(a==b)return;
if(up[a].in.find(b) != up[a].in.end())Union(a, b);
else{
//cout << "sus" << endl;
if(up[a].out.find(b) != up[a].out.end())return;
ans -= up[b].root;
up[a].out.insert(b);
up[b].in.insert(a);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while(m--){
int a, b;
cin >> a >> b;
edges.push({a, b});
while(!edges.empty()){
auto x = edges.front();
edges.pop();
add(x.f, x.s);
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
30804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
30804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
30804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
