用n表示图中顶点数目，用e表示图中边或弧的数目（若图中边或弧上有权，则该图称为网）

• 稀疏图: e < nlogn 邻接表存储
• 稠密图: e > nlogn 邻接矩阵存储

原因：
1. 邻接表只存储非零节点，而邻接矩阵则要把所有的节点信息(非零节点与零节点)都存储下来。
2. 稀疏图的非零节点不多，所以选用邻接表效率高，如果选用稠密图就会造成很多空间的浪费，矩阵中大多数都会是零节点！稠密图的非零界点多，零节点少，选用邻接矩阵是最适合不过！

//有向图拓扑排序
vector<vector<int>> e;
vector<int> deg;
vector<int> topsort(int n, vector<vector<int>> &cond) {
    e.clear(); e.resize(n + 1, vector<int>());
    deg.clear(); deg.resize(n + 1);

    for (auto &vec : cond) {
        e[vec[0]].push_back(vec[1]);
        deg[vec[1]]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) if (deg[i] == 0) q.push(i);
    vector<int> ret(n + 1);
    int now = 0;
    while (!q.empty()) {
        int sn = q.front(); q.pop();
        ret[sn] = now; now++;
        for (int fn : e[sn]) {
            deg[fn]--;
            if (deg[fn] == 0) q.push(fn);
        }
    }
    if (now != n) ret[0] = -1;  //没有合理的拓扑排序，将首个设为-1，方便后续判断
    return ret;
}



//无向图求最大环
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,vector<int>>ma;
int vis[N], a, b, cas, n, m, ans;  
//vis[]表示遍历到的当前点是第几个，如果有点被重复遍历到，那中间这段距离就是环的大小
int dfs (int i, int no)
{
    vis[i] = no;
    for (int j = 0; j < ma[i].size(); ++j)
    {
        if (!vis[ma[i][j]]) dfs (ma[i][j], no + 1);
        else ans = max (ans, no - vis[ma[i][j]] + 1);
    }
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) ma[i].clear();
    for (int i = 1; i <= m; ++i)
    {
        scanf ("%d%d", &a, &b);
        ma[a].emplace_back (b);
        ma[b].emplace_back (a);
    }
    ans = 0;
    memset (vis, 0, sizeof (vis));
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs (i, 1);

    if (ans >= 3) pcout<<ans<<endl;
    else cout<<0<<endl;

    return 0;
}


//有向图求最大环
#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5;

int v[maxn],cnt[maxn],N;
int res;
bool vis[maxn];
queue<int> Q;

void TopSort () {
    while (!Q.empty()) {
        Q.pop();
    }
    for (int i = 1; i <= N; i++) {
        if (cnt[i] == 0) {
            Q.push(i);
        }
    }
    int now;
    while (!Q.empty()) {
        now = Q.front();
        Q.pop();
        vis[now] = true;
        cnt[v[now]]--;
        if (cnt[v[now]] == 0) {
            Q.push(v[now]);
        }
    }
}

void DFS (int idx, int cnt) {
    if (!vis[idx])
        vis[idx] = true,DFS(v[idx], cnt+1);
    else
        res = max(res, cnt);
}

int main() {
    cin >> N;
    memset(cnt, 0, sizeof(cnt));
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= N; i++) {
        cin >> v[i];
        cnt[v[i]]++; //入度++
    }
    TopSort(); //把不是环的check
    res = 0;
    for (int i = 1; i <= N; i++) {
        if (!vis[i]) 
            DFS(i, 0);
    }
    cout << res << endl;
    return 0;
}


//有向图判环（拓扑排序）,如果图中有某个点出入度都为0，那么其肯定是独立的，那么这个图就不是连通的
unordered_map<int,vector<int>>g;
vector<int> Indeg(n * m);
bool cheak(){
    queue<int> q;
    for(int i = 0; i < n * m; i++) {
        if(Indeg[i] == 0) q.emplace(i);
    } 

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(auto &next : g[cur]) {
            Indeg[next]--;
            if(Indeg[next] == 0) q.emplace(next);
        }
    }

    bool loop = false;
    for(int i = 0; i < n * m; ++i) {
        // 仍有点入度不为0，说明有环
        if(Indeg[i] != 0) {
            loop = true;
            break;
        }
    }
    return loop;
}



//并查集判环及个数（无向图）
int n, m, u, v, p[N], cnt, res;
int find(int x) {
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}
void cheak(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) p[i] = i;
    while (m --) {
        cin >> u >> v;
        u = find(u), v = find(v);
        if (u != v) {
            p[u] = v;
        } else {
            cnt ++;   //环的个数
        }
    }
    for (int i = 1; i <= n; i ++) 
        res += p[i] == i;  //如果图是连通的，那么最后res只会为1
}

//补充：也可以通过p[i]==i判断集合个数
if(p[i]==i)     //若元素的父亲是它本身，那么集合数+1
    num++;

// 递归的路径压缩
int find(int x)
{
    return x == p[x] ? x : (p[x] = find(p[x]));
}

//按秩合并
void union(int x1, int x2)
{
    int f1 = find(x1);
    int f2 = find(x2);
    if (rank[f1] > rank[f2]){
        p[f2] = f1;
    } else{
        p[f1] = f2;
        if(rank[f1] == rank[f2]){
            ++rank[f2];
        }
    }
}

两种优化的比较：
都是以减少查询的代价（缩短查询路径）为目的，因为并查集合并集合的复杂度是O（1），只有查询稍显麻烦
两种优化可以同时进行，查询操作几乎可以降到O（1）
路径压缩的优化程度更高，所以一般用路径压缩就足够了
但是路径压缩会破坏树的结构，在一些情况下是不能使用的，按秩合并则不会