#include <bits/stdc++.h>
using namespace std;
#define ll long long
int pa[100000];
ll ans=0;
set<int>in[100000],out[100000],pain[100000];
int sz[100000];
int par(int x)
{
if(pa[x]==x)
return x;
pa[x]=par(pa[x]);
return pa[x];
}
void un(int x,int y)
{
x=par(x);
y=par(y);
if(x==y)
{
return ;
}
if(sz[x]<sz[y])
swap(x,y);
///dont forget the sz[x]+=sz[y];sz[y]=0;
pa[y]=x;
ans-=sz[x]*in[x].size();
ans-=sz[y]*in[y].size();
for(auto i:in[y])
{
if(in[x].find(i)!=in[x].end())
continue;
in[x].insert(i);
}
ans+=in[x].size()*(sz[x]+sz[y]);
for(auto i:out[y])
{
if(out[x].find(i)!=out[x].end())
continue;
out[x].insert(i);
pain[i].erase(y);
pain[i].insert(x);
}
sz[x]+=sz[y];
sz[y]=0;
}
int main()
{
//os_base::sync_with_stdio(0);
cout.tie(0);
int n;
cin>>n;
int m;
ans=n;
for(int i=0;i<n;i++)
{
sz[i]=1;
pa[i]=i;
in[i].insert(i);
}
cin>>m;
while(m--)
{
int x,y;
cin>>x>>y;
x--;
y--;
if(par(x)==par(y))
{
// cout<<1<<' ';
cout<<ans-n<<endl;
continue;
}
if(pain[par(x)].find(par(y))!=pain[par(x)].end())
{
// cout<<2<<' ';
un(x,y);
cout<<ans-n<<endl;
continue;
}
if(in[par(y)].find(x)!=in[par(y)].end())
{
//cout<<3<<' ';
cout<<ans-n<<endl;
continue;
}
in[par(y)].insert(x);
out[par(x)].insert(par(y));
pain[par(y)].insert(par(x));
ans+=sz[par(y)];
//cout<<4<<' ';
cout<<ans-n<<endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
14292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
14292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
14292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
