Submission #74368453

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[100010], r[100010];
int t, bt[100010], c[100010];
void dfs(int u){
    bt[u] = t;
    for (int v : e[u])if (!bt[v])c[v] = (c[u] + 1) % 3, dfs(v);
    for (int v : r[u])if (!bt[v])c[v] = (c[u] + 2) % 3, dfs(v);
}
bool sc[100010];
int ct[100010][3];
int ce[100010];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    while (m--){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        r[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i)if (!bt[i])++t, sc[t] = 1, dfs(i);
    for (int i = 1; i <= n; ++i){
        ++ct[bt[i]][c[i]];
        for (int j : e[i])
            sc[bt[i]] &= c[j] == (c[i] + 1) % 3, ++ce[bt[i]];
    }
    long long rs = 0;
    for (int i = 1; i <= t; ++i){
        if (!sc[i]){
            int s = ct[i][0] + ct[i][1] + ct[i][2];
            rs += 1ll * s * s;
        } else {
            if (ct[i][0] && ct[i][1] && ct[i][2])
                rs += 1ll * ct[i][0] * ct[i][1] + 1ll * ct[i][1] * ct[i][2] + 1ll * ct[i][2] * ct[i][0];
            else rs += ce[i];
        }
    }
    cout << rs << endl;
    return 0;
}

Submission Info

Judge Result