https://www.luogu.com.cn/problem/AT2167

挺有意思的一题

考虑把点看成一条边

如 果 存 在 边 ( u , v ) , ( v , z ) 则 存 在 ( z , u ) 如果存在边(u,v),(v,z)则存在(z,u) 如果存在边(u,v),(v,z)则存在(z,u)

考虑用012三种颜色染色

如果不能染色，那么这个弱联通块最终一定是会连成一个完全图
那么他的贡献就是 s i z e ∗ s i z e size*size size∗size
如果可以只两种或一种颜色染色，那么肯定是一层连向另一层，那么直接把边数加起来即可

否则可以发现所有的0最终一定会向所有的1连边，1一定会向所有的2连边
那么直接乘起来再加起来即可

code:

#include<bits/stdc++.h>
#define N 200050
#define ll long long
using namespace std;
struct edge {
    int v, nxt, c;
} e[N << 1];
int p[N], eid;
void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}
void insert(int u, int v, int c) {
    e[eid].v = v;
    e[eid].nxt = p[u];
    e[eid].c = c;
    p[u] = eid ++;
}
int cnt[N], col[N], f, gs, gsm, n, m, vis[N];
void dfs(int u) {
    cnt[col[u]] ++; vis[u] = 1; gs ++;
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        int v = e[i].v, c = e[i].c;
        if(c == 1) gsm ++;
        if(!vis[v]) col[v] = (col[u] + c + 3) % 3, dfs(v);
        else if((col[u] + c + 3) % 3 != col[v]) f = 1;
    }
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);
        insert(u, v, 1), insert(v, u, -1);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i ++) if(!vis[i]) {
        cnt[0] = cnt[1] = cnt[2] = 0;
        f = gs = gsm = 0;
        dfs(i);
        if(f) ans += 1ll * gs * gs;
        else if(cnt[0] && cnt[1] && cnt[2]) ans += 1ll * cnt[0] * cnt[1] + 1ll * cnt[1] * cnt[2] + 1ll * cnt[2] * cnt[0];
        else ans += gsm;
    }
    printf("%lld", ans);
    return 0;
}

思维难度挺大的，考场上不一定能想出来
思维还是要开放一些