求助解惑!缩点之后判断入度为scc-1与出度为0答案为什么不一样
查看原帖
求助解惑!缩点之后判断入度为scc-1与出度为0答案为什么不一样
388782
LiZz31楼主2024/3/8 16:56

判断入度为(sccCnt - 1) 68pts

for(int i = 1;i <= cowCnt;i++){
            for(auto j:e[i]){
                if(scc[i] != scc[j]){
                    s[scc[j]].insert(scc[i]);
                }
            }
        }
        int ans = 0;
        for(int i = 1;i <= sccCnt;i++){
            if(s[i].size() == sccCnt - 1){
                ans += siz[i];
            }
        }
        cout<<ans;

判断出度为0加特判 100pts

int zero = 0;
    int sum = 0;
    for(int i = 1;i <= cowCnt;i++){
        for(auto j: e[i]){
            if(scc[i] != scc[j]){
                dout[scc[i]]++;
            }
        }
    }
    for(int i = 1;i <= sccCnt;i++){
        if(dout[i] == 0){
            zero++;
            sum = siz[i];
        }
    }
    if(zero > 1){
        sum = 0;
    }
    cout<<sum;
2024/3/8 16:56
加载中...