关于重边判定的疑问（带注释）

由于该题无法用book数组标记的方式暴力判重边

我就想了个馊主意：

先对邻接表存的图排序，在topo过程中对V[i][j] == V[i]j - 1的情况直接continue，具体如代码

/*
题目对概念的叙述有些复杂，但弄懂后其实很简单
1.强连通分量一定是连通子图。所以缩点，再找连通子图即可
2.缩点后，原图变为DAG（有向无环图）。对与DAG来说，其半连通子图一定是一条链
  可以想，若是一条链出现分叉，因为是DAG，所以分叉是无法互相到达的，也就构不成半连通子图
3.想到这里本题思路大概清晰了：先缩点，接着求最长链，最后在DAG上dp求出最长链个数 
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;

ll n, m, mod;//和题目叙述的作用一样：点数、边数及取模对象 

vector<ll> V[114514]; //存图 
vector<ll> V1[114514]; //存新图 

ll dfn[114514], low[114514];

ll stsum, scsum, dfncnt;

ll ynst[114514], st[114514];

ll blt[114514];

queue<ll> Q;

ll ru[114514];

ll ans[114514];// 这个是储存topo到各强连通分量时最长链的长度 

ll scsize[114514]; //这里虽然缩成了点，但计算最长链上的点是还是要把强连通分量里所有的点算进去的 

ll cnt[114514];// 储存走到点x的最长链的数量 

void tarjan(ll x) {
    dfncnt++;
    low[x] = dfncnt;
    dfn[x] = dfncnt;
    stsum++;
    ynst[x] = 1;
    st[stsum] = x;
    for (int i = 0; i < V[x].size(); i++) {
        if (dfn[V[x][i]] == 0) {
            tarjan(V[x][i]);
            low[x] = min(low[x], low[V[x][i]]);
        } else if (ynst[V[x][i]] == 1) {
            low[x] = min(low[x], dfn[V[x][i]]);
        }
    }
    if (dfn[x] == low[x]) {
        scsum++;
        while (st[stsum] != x) {
            ynst[st[stsum]] = 0;
            blt[st[stsum]] = scsum;
            scsize[scsum]++;
            stsum--;
        }
        ynst[st[stsum]] = 0;
        scsize[scsum]++;
        blt[st[stsum]] = scsum;
        stsum--;
    }
    return;
}

int main() {
    cin >> n >> m >> mod;
    ll u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        V[u].push_back(v);
    }//建图部分     
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) {
            tarjan(i); // tarjan部分就不加太多注释了，这是今天写的第5遍，
                       //已刻进DNA，其余部分注释尽可能详细些
        }
    } 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < V[i].size(); j++) {
            if (blt[i] == blt[V[i][j]]) {
                continue;
            }
            V1[blt[i]].push_back(blt[V[i][j]]);
            ru[blt[V[i][j]]]++;
        }
    } 
/*
这里开始建新图，我们敲模板时已经很熟悉流程了，but
由于这里不仅要求最长链，还要求最长链计数，那么就必须要判重边！
写到这里自然就理解了 
*/   
    for (int i = 1; i <= scsum; i++) {
        sort(V1[i].begin(), V1[i].end());
    }//点太多了（悲），但想出了排序这个sou注意来判重边
    for (int i = 1; i <= scsum; i++) { // 这里开始topo环节 
        if (ru[i] == 0) {
            Q.push(i);
        }
        ans[i] = scsize[i];
        cnt[i] = 1;
    }
    ll t;
    while (Q.size()) {
        t = Q.front();
        Q.pop();
        for (int i = 0; i < V1[t].size(); i++) {
            if (i > 0 && V1[t][i] == V1[t][i - 1]) {
                continue;
            }//这就是我判重边的方法。。。 
            if (ans[V1[t][i]] == ans[t] + scsize[V1[t][i]]) { // 在这种情况下，只更新走到该点时的最长链数量 
                cnt[V1[t][i]] += cnt[t];
                cnt[V1[t][i]] = cnt[V1[t][i]] % mod;
            } else if (ans[V1[t][i]] < ans[t] + scsize[V1[t][i]]) { // 更新走到该点时的最长链长度，并更新其数量 
                ans[V1[t][i]] = ans[t] + scsize[V1[t][i]];
                cnt[V1[t][i]] = cnt[t];     
            }
            ru[V1[t][i]]--;
            if (!ru[V1[t][i]]) {
                Q.push(V1[t][i]);
            }
        }
    }
    ll fans = -0x7fffffff, fcnt = 0;
    for (int i = 1; i <= scsum; i++) {
        fans = max(fans, ans[i]);
    }
    cout << fans << endl;
    for (int i = 1; i <= scsum; i++) {
        if (fans == ans[i]) {
            fcnt += cnt[i];
            fcnt = fcnt % mod;
        }
    }
    cout << fcnt % mod;
    return 0;
}

然鹅，64pts

于是我就改了二维map，ac了

code：

/*
题目对概念的叙述有些复杂，但弄懂后其实很简单
1.强连通分量一定是连通子图。所以缩点，再找连通子图即可
2.缩点后，原图变为DAG（有向无环图）。对与DAG来说，其半连通子图一定是一条链
  可以想，若是一条链出现分叉，因为是DAG，所以分叉是无法互相到达的，也就构不成半连通子图
3.想到这里本题思路大概清晰了：先缩点，接着求最长链，最后在DAG上dp求出最长链个数 
*/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

typedef long long ll;

ll n, m, mod;//和题目叙述的作用一样：点数、边数及取模对象 

vector<ll> V[114514]; //存图 
vector<ll> V1[114514]; //存新图 

ll dfn[114514], low[114514];

ll stsum, scsum, dfncnt;

ll ynst[114514], st[114514];

ll blt[114514];

queue<ll> Q;

ll ru[114514];

ll ans[114514];// 这个是储存topo到各强连通分量时最长链的长度 

ll scsize[114514]; //这里虽然缩成了点，但计算最长链上的点是还是要把强连通分量里所有的点算进去的 

ll cnt[114514];// 储存走到点x的最长链的数量 

map<ll, map<ll, ll> > M;

void tarjan(ll x) {
    dfncnt++;
    low[x] = dfncnt;
    dfn[x] = dfncnt;
    stsum++;
    ynst[x] = 1;
    st[stsum] = x;
    for (int i = 0; i < V[x].size(); i++) {
        if (dfn[V[x][i]] == 0) {
            tarjan(V[x][i]);
            low[x] = min(low[x], low[V[x][i]]);
        } else if (ynst[V[x][i]] == 1) {
            low[x] = min(low[x], dfn[V[x][i]]);
        }
    }
    if (dfn[x] == low[x]) {
        scsum++;
        while (st[stsum] != x) {
            ynst[st[stsum]] = 0;
            blt[st[stsum]] = scsum;
            scsize[scsum]++;
            stsum--;
        }
        ynst[st[stsum]] = 0;
        scsize[scsum]++;
        blt[st[stsum]] = scsum;
        stsum--;
    }
    return;
}

int main() {
    cin >> n >> m >> mod;
    ll u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        V[u].push_back(v);
    }//建图部分     
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) {
            tarjan(i); // tarjan部分就不加太多注释了，这是今天写的第5遍，
                       //已刻进DNA，其余部分注释尽可能详细些
        }
    } 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < V[i].size(); j++) {
            if (blt[i] == blt[V[i][j]]) {
                continue;
            }
            if (M[blt[i]][blt[V[i][j]]]) {
                continue;
            }
            V1[blt[i]].push_back(blt[V[i][j]]);
            M[blt[i]][blt[V[i][j]]] = 1;
            ru[blt[V[i][j]]]++;
        }
    } 
/*
这里开始建新图，我们敲模板时已经很熟悉流程了，but
由于这里不仅要求最长链，还要求最长链计数，那么就必须要判重边！
写到这里自然就理解了 
*/   
    for (int i = 1; i <= scsum; i++) { // 这里开始topo环节 
        if (ru[i] == 0) {
            Q.push(i);
        }
        ans[i] = scsize[i];
        cnt[i] = 1;
    }
    ll t;
    while (Q.size()) {
        t = Q.front();
        Q.pop();
        for (int i = 0; i < V1[t].size(); i++) {
            if (ans[V1[t][i]] == ans[t] + scsize[V1[t][i]]) { // 在这种情况下，只更新走到该点时的最长链数量 
                cnt[V1[t][i]] += cnt[t];
                cnt[V1[t][i]] = cnt[V1[t][i]] % mod;
            } else if (ans[V1[t][i]] < ans[t] + scsize[V1[t][i]]) { // 更新走到该点时的最长链长度，并更新其数量 
                ans[V1[t][i]] = ans[t] + scsize[V1[t][i]];
                cnt[V1[t][i]] = cnt[t];     
            }
            ru[V1[t][i]]--;
            if (!ru[V1[t][i]]) {
                Q.push(V1[t][i]);
            }
        }
    }
    ll fans = -0x7fffffff, fcnt = 0;
    for (int i = 1; i <= scsum; i++) {
        fans = max(fans, ans[i]);
    }
    cout << fans << endl;
    for (int i = 1; i <= scsum; i++) {
        if (fans == ans[i]) {
            fcnt += cnt[i];
            fcnt = fcnt % mod;
        }
    }
    cout << fcnt % mod;
    return 0;
}

蒟蒻不懂啊，排序的判重边方法为啥就不行呢？