题解
暴力方法:
遍历每个节点,遍历每个节点的子节点,遍历每个子节点的子节点,看看子子节点是否是节点的子节点,时间复杂度 \(O(nm^2)\)
优化
考虑无向边建边的时候建成有向边,且两个点建边时,度数小的指向度数大的,如果度数相等,编号小的指向编号大的(其实这一步是为了避免重复计数)(启发式建边???)时间复杂度 \(O(m\sqrt{m})\)
证明:
每个节点,最多有 \(\sqrt{m}\) 条出边,如果原始无向图中,某个点有 \(k\) 条边
-
如果 \(k<\sqrt{m}\) 那么其出边也不会超过 \(\sqrt{m}\)
-
如果 \(k\geq \sqrt{m}\) 那么其只会指向边比它更多的点,这样的点不超过 \(\sqrt{m}\)
所以相当于遍历每个有向边,然后遍历终点的出边,查看是否也是起点的一条出边的终点(因为不存在有向三元环,这样也避免了重复计数)
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> G[100005];
int out[100005]={0};
int vis[100005]={0};
int a[200005]={0};//edge
int b[200005]={0};
int du[100005]={0};
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
du[a[i]]++;
du[b[i]]++;
}
for(int i=1;i<=m;i++)
{
int x=a[i],y=b[i];
if(du[x]>du[y]) G[y].push_back(x);
else if(du[x]<du[y]) G[x].push_back(y);
else if(x<y) G[x].push_back(y);
else G[y].push_back(x);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(auto it:G[i]) vis[it]=i;
for(auto next:G[i])
{
for(auto nnext:G[next])
{
if(vis[nnext]==i) ans++;
}
}
}
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
标签:遍历,int,sqrt,100005,计数,无向,du,节点,P1989
From: https://www.cnblogs.com/pure4knowledge/p/18326836