发布时间：2024-07-31

环计数问题

普通环计数

给定一个简单图，求图中简单环的数目。简单环是指没有重复顶点或边的环。

• 状态压缩，$f_{s,i}$表示到节点$i$，走过的集合为$s$，且第一个点是$s$中最低位代表的点的路径数量
• 这样会把二元环计算进去，并且每个环会算两次，答案为$\frac{ans-m}{2}$
• 复杂度$O(2^nm)$

int f[1<<19][20];
vector<int> adj[20];
int ans;
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<n;i++){
        f[1<<i][i]=1;
    }
    for(int s=1;s<1<<n;s++){
        for(int i=0;i<n;i++){
            if(!f[s][i])continue;
            for(auto j:adj[i]){
                if((s&-s)>(1ll<<j))continue;
                if(s>>j&1){
                    if((s&-s)==(1ll<<j))ans+=f[s][i];
                }
                else f[s|(1ll<<j)][j]+=f[s][i];
            }
        }
    }
    cout<<(ans-m)/2<<"\n";
}

无向图三元环计数问题

• 小度数向大度数连边，相等则小编号向大编号连边
• 然后暴力
• 可以证明是 $m\sqrt m$的复杂度

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> din(n+1),adj[n+1];
    vector<array<int,2>> e(m);
    for(auto &[u,v]:e){
        cin>>u>>v;
        din[u]++;
        din[v]++;
    }
    int ans=0;
    vector<int> vis(n+1);
    for(auto &[u,v]:e){
        if(din[u]>din[v]||(din[u]==din[v]&&u>v)){
            swap(u,v);
        }
        adj[u].push_back(v);
    }
    for(int u=1;u<=n;u++){
        for(auto v:adj[u])vis[v]=u;
        for(auto v:adj[u]){
            for(auto w:adj[v]){
                if(vis[w]==u)ans++;
            }
        }
    }
    cout<<ans<<"\n";
}

四元环计数

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v);
    E[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  for (int u = 1; u <= n; u++)
    for (int v : E[u])
      if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) E1[u].push_back(v);
  for (int a = 1; a <= n; a++) {
    for (int b : E1[a])
      for (int c : E[b]) {
        if (deg[a] < deg[c] || (deg[a] == deg[c] && a <= c)) continue;
        total += cnt[c]++;
      }
    for (int b : E1[a])
      for (int c : E[b]) cnt[c] = 0;
  }
  cout << total << '\n';
  return 0;
}