hdu 3184 三元环计数_uu3184

Counting Stars

思路： 我们发现每一个星结构其实就是共享一条边的两个三元环，所以我们要做的就是对每一条边进行计数看其能组成几个不同的三元环。 然后C（x，2）就是答案

代码1：(要慢一点 )

//方法一： m * sqrt(m)
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int N =1e5+5;
const ll lim=1e5+5;
 
int deg[N];
set<ll >se;
vector< int >ve[N];
int vis[N];
int n,m;
int _hs[N];
 
void init()
{
    memset(vis,0,sizeof(vis));
    memset(deg,0,sizeof(deg));
    se.clear();
    memset(_hs,0,sizeof(_hs));
    for(int i=0;i<N;i++) ve[i].clear();
    return ;
}
 
void solve()
{
    int up=sqrt(1.0*m);
    ll ans=0;
    for(int a=1;a<=n;a++)
    {
        vis[a]=1;
        for(int i=0;i<ve[a].size();i++) _hs[ve[a][i]]=a;
        for(int i=0;i<ve[a].size();i++){
            int b=ve[a][i];
            if(vis[b]) continue;
 
            ll cnt=0;
            if(deg[b]<=up)
            {
                for(int j=0;j<ve[b].size();j++){
                    int c=ve[b][j];
                    if(_hs[c]==a) cnt++;
                }
            }
            else{
                for(int j=0;j<ve[a].size();j++){
                    int c=ve[a][j];
                    if(se.find(ll(b*lim+c))!=se.end()) cnt++;
                }
            }
 
            ans=ans+cnt*(cnt-1)/2;
        }
    }
 
    printf("%lld\n",ans);
}
 
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        init();
        int u,v;
        for(int i=1;i<=m;i++)
        {
           scanf("%d %d",&u,&v);
           deg[u]++;
           deg[v]++;
           se.insert(ll(u*lim+v));
           se.insert(ll(v*lim+u));
           ve[u].push_back(v);
           ve[v].push_back(u);
        }
        solve();
 
    }
    return 0;
}

代码2 ：（定义图的方向，建成有向无环图 遍历的时候更快一些）

//单向建图 建图完毕后为有向无环图
 
#include<bits/stdc++.h>
#define LL long long
using namespace std;
typedef pair<int ,int > pii;
typedef long long ll;
const int N =1e5+5;
const int M =2e5+5;
const ll lim=1e5+5;
 
ll cnt[M];
int deg[N];
int x[M];
int y[M];
vector<pii>ve[N];
int n,m;
int pos[N];
int jud[N];
 
 
void solve()
{
    //ll tot=0;   三元环个数
    for(int i=1;i<=m;i++)
    {
        int u=x[i]; int v=y[i];
        for(int j=0;j<ve[u].size();j++){
            int uu=ve[u][j].first;
            int inde=ve[u][j].second;
            pos[uu]=inde;
            jud[uu]=i+1;
        }
 
        for(int j=0;j<ve[v].size();j++)
        {
            int vv=ve[v][j].first;
            if(jud[vv]==i+1){
                //tot++;
                cnt[i]++;       // 三元环对应的三条边分别 ++
                cnt[pos[vv]]++;
                cnt[ve[v][j].second]++;
            }
        }
    }
 
    //cout<<tot<<endl;
    ll ans=0;
    for(int i=1;i<=m;i++){
        ans=ans+cnt[i]*(cnt[i]-1)/2;
    }
    printf("%lld\n",ans);
}
 
void init()
{
    for(int i=0;i<=n;i++){
        deg[i]=pos[i]=jud[i]=0;
        ve[i].clear();
    }
}
 
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        init();
        int u,v;
        for(int i=1;i<=m;i++){
            scanf("%d %d",&u,&v);
            deg[u]++; deg[v]++;
            x[i]=u;  y[i]=v;
        }
 
        for(int i=1;i<=m;i++){
            cnt[i]=0;
            if(deg[x[i]]<deg[y[i]]){
                ve[x[i]].push_back(pii(y[i],i));
            }
            else if(deg[x[i]]>deg[y[i]]){
                ve[y[i]].push_back(pii(x[i],i));
            }
            else{
                if(x[i]<=y[i]){
                    ve[x[i]].push_back(pii(y[i],i));
                }
                else ve[y[i]].push_back(pii(x[i],i));
            }
        }
        /*
        for(int i=1;i<=n;i++) cout<<ve[i].size()<<" ";
        cout<<endl;
        */
        solve();
 
    }
    return 0;
}