无向图求三元环_三元循环在无向图中寻找cot

无向图是一个稀疏图，点$n < 10^5$ 边数$m < min(10^5,\frac{n\times(n-1)}{2})$,现在给出n,m,E(边集合)，求出这个三元环的个数，两个三元环不同是：当于对两个三元环的边，某个三元环存在一条边在另一个三元环中无法找到。
解法：暴力的方法可以使复杂度达到$O(m\times\sqrt{m})$.具体解法如下：
首先我们先是记录，使用邻接表记录无向图，记录每个点的出度，每条边用hash存下来，这个如何存呢，可以把边转换成一个独一无二的数，假设这条边端点是ab，可以存下$a\times n+b$ 和 $b \times n + a$,用set，map存都可以，这样如果我们得到两个点看是否相连，就看在set中是否能找到这个数。
储存过程结束后，开始从1-n枚举每个点设为x，然后找到所有和x相连的点记为y，并用link数组记录下link[y] = x，（此时相当于枚举了一条边）因为要找三元环，如果存在，另两个点肯定是和x相连的，这个时候分成两类
一：如果y点出度小于等于$\sqrt{m}$,那么就直接继续找和y相连的点，如果和y相连的点z发现 link[z] = x,说明这个点z也是和x联通的，“然后找到所有和x相连的点记为y，并用link数组记录下link[y] = x”在z点实际是在这一步标记的。这样我们就是找到一个个数加一
二：如果y点出度大于$\sqrt{m}$,那么我们从x的基础上，继续找一个点z，看z和y是否相连，判断方法就是计算$z\times n + y$ 是否可以在set中找到，如果找到个数加一。
最终就完成了寻找，但是每个点都查找重复了三次，最后结果需要除以3。
复杂度分析：
为了方便说明我们按照上面叙述的算法，记枚举的第一个点为x，第二个点为y，最后一个点为z，
枚举的边用两端点表示如枚举的第一条边xy
下面进行分类讨论：
第一类点y的出度<=$\sqrt{m}$,那么我们便继续枚举y的连接点z，这时候我们最多枚举的xy边（第一条边）有m条，每枚举完第一条边后，因为y的出度<=$\sqrt{m}$,所以在枚举完第一条边的基础上，最多每次枚举$\sqrt{m}$条边，所以此时的复杂度为O(m$\sqrt{m}$)
第二类点y的出度>$\sqrt{m}$,此时我们不在y点向外找点，我们回到x，找到另个与x相连的点z，此时找两个点所花费的复杂度大约是$\sqrt{m}$*$\sqrt{m}$=m，因为这样的y点不会超过$\sqrt{m}$个，所以总的复杂度就是O(m$\sqrt{m}$)
综上所述复杂度是O(m$\sqrt{m}$)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
vector<int>G[maxn];
set<ll>st;
int vis[maxn],link[maxn],out[maxn];
int main(){
    ll ans,sum;
    int n,m,i,j,k,x,y,z,B;
    while(scanf("%d%d",&n,&m) != EOF){
        //初始化
        B = sqrt(m);
        st.clear();
        for(i = 1; i <= n; i++){
            G[i].clear();
            vis[i] = out[i] = link[i] = 0;
        }
        for(i = 1; i <= m; i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            out[x]++;
            G[y].push_back(x);
            out[y]++;
            st.insert((ll)x*n+y);//hash存边
            st.insert((ll)y*n+x);
        }
        ans = 0;
        for(i = 1; i <= n; i++){//枚举第一个点
            x = i;
            vis[x] = 1;//标记
            for(j = 0; j < G[x].size(); j++)
                link[G[x][j]] = x;
            for(j = 0; j < G[x].size(); j++){
                sum = 0;
                y = G[x][j];//枚举第二个点，枚举了第一条边
                if(vis[y])
                    continue;
                if(out[y] <= B){//第一类
                    for(k = 0; k < G[y].size(); k++){
                        z = G[y][k];
                        if(link[z] == x)
                            sum++;
                    }
                }
                else{//第二类
                    for(k = 0; k < G[x].size(); k++){
                        z = G[x][k];
                        if(st.find((ll)z*n+y) != st.end())
                            sum++;
                    }
                }
                ans += sum;
            }
        }
        printf("%lld\n",ans/3);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60