Submission #986139

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int NMAX = 100005;

vector<pair<int, int>> G[NMAX];
int cnt[3], cntAll = 0;
int cntEdges = 0;
bool used[NMAX];
int values[NMAX];

bool complete;

void dfs(int node) {
    used[node] = true;
    cnt[values[node]]++;
    cntAll++;
    cntEdges += SZ(G[node]);
    for (const pair<int, int>& p: G[node]) {
        int to = p.first;
        int add = p.second;
        if (!used[to]) {
            values[to] = (values[node] + add) % 3;
            dfs(to);
        } else {
            if (values[to] != (values[node] + add) % 3) {
                complete = true;
            }
        }
    }
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(make_pair(y, 1));
        G[y].push_back(make_pair(x, 2));
    }
    int64_t ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            memset(cnt, 0, sizeof cnt);
            cntAll = 0;
            cntEdges = 0;
            complete = false;
            dfs(i);
            cntEdges /= 2;
            if (complete) {
                ans += (int64_t) cntAll * cntAll;
            } else if (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
                ans += (int64_t) cnt[0] * cnt[1] +
                    (int64_t) cnt[1] * cnt[2] +
                    (int64_t) cnt[2] * cnt[0];
            } else {
                ans += cntEdges;
            }
        }
    }
    cout << ans << '\n';
}

Submission Info

Judge Result