#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
int n,m;
int par[MAXN];
ll sz[MAXN];
set<int>edges_in[MAXN];
set<int>edges_out[MAXN];
set<int>comp[MAXN];
ll ans=0;
int getRoot(int u)
{
if(u==par[u])return u;
return par[u]=getRoot(par[u]);
}
ll cnt(int u)
{
return sz[u]*(sz[u]-1ll)+edges_in[u].size()*sz[u];
}
stack<pair<int,int> >merges;
void merge(int a,int b)
{
a=getRoot(a);b=getRoot(b);
if(a==b)return;
if(edges_in[b].size()+edges_out[b].size()>edges_in[a].size()+edges_out[a].size())swap(a,b);
for(auto xd:edges_in[b])
{
int t=getRoot(xd);
if(t==a)
{
continue;
}
edges_out[t].erase(b);
edges_out[t].insert(a);
edges_in[a].insert(t);
if(edges_out[a].find(t)!=edges_out[a].end())
{
merges.push({t,a});
}
}
for(auto xd:edges_out[b])
{
int t=getRoot(xd);
if(t==a)continue;
edges_out[a].insert(t);
edges_in[t].erase(b);
edges_in[t].insert(a);
if(edges_in[a].find(t)!=edges_in[a].end())
{
merges.push({t,a});
}
}
edges_in[a].erase(b);
edges_out[a].erase(b);
for(auto xd:comp[b])
{
edges_in[a].erase(xd);
edges_out[a].erase(xd);
comp[a].insert(xd);
}
par[b]=a;
sz[a]+=sz[b];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
par[i]=i;comp[i].insert(i);
sz[i]=1;
}
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
a=getRoot(a);
b=getRoot(b);
if(a==b)
{
//cout<<ans<<endl;
//continue;
}
else
{
if(edges_in[a].find(b)!=edges_in[a].end())
{
merges.push({a,b});
int x,y;
while(!merges.empty())
{
tie(x,y)=merges.top();merges.pop();
x=getRoot(x);y=getRoot(y);
if(x!=y)
{
ans-=cnt(x);
ans-=cnt(y);
merge(x,y);
ans+=cnt(getRoot(x));
}
//ans+=cnt(getRoot(y));
}
}
else if(edges_in[b].find(a)==edges_in[b].end())
{
ans-=cnt(b);
edges_in[b].insert(a);
edges_out[a].insert(b);
ans+=cnt(b);
}
/*for(int j=1;j<=n;j++)
{
cout<<getRoot(j)<<" ";
}
cout<<endl;
for(int j=1;j<=n;j++)
{
cout<<cnt(getRoot(j))<<" ";
}
cout<<endl;
cout<<ans<<endl;
*/
ll sum=0;
for(int j=1;j<=n;j++)
{
if(j==getRoot(j))
{
sum+=cnt(j);
}
}
cout<<sum<<endl;
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
14392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
14392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
14392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
