#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m;
struct dsu{
int par[maxn],sz[maxn],szkho[maxn],szvo[maxn];
long long res=0;
set<int>vorod[maxn],khoroj[maxn];
dsu(){
for(int i=1;i<maxn;i++){
par[i]=i;
sz[i]=1;
}
};
int root(int u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
void con(int u,int v){
u=root(u);v=root(v);
// cout<<"con: "<<u<<" "<<v<<" "<<sz[u]<<" "<<sz[v]<<"\n";
if(u==v){
return ;
}
vector<pair<int,int>>allq;
if(sz[u]==1&&sz[v]==1){
for(auto x:vorod[u]){
res--;
khoroj[x].erase(u);
allq.push_back(make_pair(x,u));
}
for(auto x:khoroj[u])
{
res-=sz[x];
szvo[x]--;
vorod[x].erase(u);
allq.push_back(make_pair(u,x));
}
for(auto x:vorod[v]){
res--;
khoroj[x].erase(v);
allq.push_back(make_pair(x,v));
}
for(auto x:khoroj[v])
{
res-=sz[x];
szvo[x]--;
vorod[x].erase(v);
allq.push_back(make_pair(v,x));
}
res+=2;
vorod[u].clear();
khoroj[u].clear();
vorod[v].clear();
khoroj[v].clear();
par[u]=v;
sz[v]+=sz[u];
szvo[u]=szvo[v]=szkho[u]=szkho[v]=0;
}
else if(sz[u]==1||sz[v]==1){
if(sz[v]==1){
swap(u,v);
}
for(auto x:vorod[u]){
res--;
khoroj[x].erase(u);
allq.push_back(make_pair(x,u));
}
for(auto x:khoroj[u])
{
res-=sz[x];
szvo[x]--;
vorod[x].erase(u);
allq.push_back(make_pair(u,x));
}
// cout<<"salam: "<<res<<" "<<szkho[v]<<" "<<szvo[v]<<"\n";
res+=2ll*sz[v]*sz[u];
res+=1ll*sz[u]*(szkho[v]+szvo[v]);
sz[v]+=1;
par[u]=v;
vorod[u].clear();
khoroj[u].clear();
}
else{
if(sz[u]>sz[v]){
swap(u,v);
}
for(auto x:vorod[u]){
res-=1ll*sz[u]*sz[x];
khoroj[x].erase(u);
allq.push_back(make_pair(x,u));
}
for(auto x:khoroj[u]){
res-=1ll*sz[u]*sz[x];
vorod[x].erase(u);
allq.push_back(make_pair(u,x));
}
res+=1ll*sz[u]*sz[v]*2;
res+=1ll*sz[u]*(szkho[v]+szvo[v]);
vorod[u].clear();
khoroj[u].clear();
sz[v]+=sz[u];
par[u]=v;
}
for(auto x:allq){
add(x.first,x.second);
}
}
void add(int u,int v){
u=root(u);
v=root(v);
// cout<<"add: "<<u<<" "<<v<<" "<<sz[u]<<" "<<sz[v]<<"\n";
if(u==v){
return ;
}
if(sz[u]==sz[v]&&sz[u]==1){
if(khoroj[u].count(v)!=0){
return ;
}
res++;
khoroj[u].insert(v);
vorod[v].insert(u);
szvo[v]++;
if(khoroj[v].count(u)!=0){
con(u,v);
}
}
else if(sz[u]==1){
if(khoroj[u].count(v)!=0){
return ;
}
res+=sz[v];
khoroj[u].insert(v);
vorod[v].insert(u);
szvo[v]++;
// cout<<"inja: "<<v<<" "<<szvo[v]<<"\n";
if(vorod[u].count(v)!=0){
con(u,v);
}
}
else if(sz[v]==1){
if(vorod[v].count(u)!=0){
return ;
}
res++;
vorod[v].insert(u);
szvo[v]+=sz[u];
if(khoroj[v].count(u)!=0){
con(u,v);
}
}
else{
if(khoroj[u].count(v)!=0){
return ;
}
res+=sz[u]*sz[v];
vorod[v].insert(u);
khoroj[u].insert(v);
szvo[v]+=sz[u];
szkho[u]+=sz[v];
if(vorod[u].count(v)!=0){
con(u,v);
}
}
}
}ds;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
ds.add(u,v);
cout<<ds.res<<"\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
