This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<vector>
#include<algorithm>
std::vector<int> a[111111];
int p[111111];
int q[111111];
int par(int x){return x==p[x]?x:p[x]=par(p[x]);}
void com(int x,int y){x=par(x);y=par(y);if(x!=y){p[x]=y;q[y]+=q[x];}}
int main()
{
long long res;
int i,j,n,m;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&i,&j);
a[i].push_back(j);
}
for(i=1;i<=n;i++)
{
p[i]=i;
q[i]=1;
std::sort(a[i].begin(),a[i].end());
}
for(i=1;i<=n;i++)
{
if(!a[i].empty()&&binary_search(a[a[i][0]].begin(),a[a[i][0]].end(),i))com(a[i][0],i);
for(j=1;j<a[i].size();j++)
{
com(a[i][j],a[i][0]);
if(binary_search(a[a[i][j]].begin(),a[a[i][j]].end(),i))com(a[i][j],i);
}
}
res=0;
for(i=1;i<=n;i++)
{
if(i==p[i])res+=1LL*q[i]*(q[i]-1);
for(j=0;j<a[i].size();j++)if(par(i)!=par(a[i][j]))res++;
}
printf("%lld\n",res);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |