Witch game

#include<bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;
ll n, m, used[200000], r, d[200000], c, s;
vector < ll > k;
set < ll > g[200000];
void dfs(int v)
{
    used[v] = 1;
    r++;
    for (auto u: g[v])
        if (!used[u]) dfs(u);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        g[i].insert(x);
        g[x].insert(i);
    }
    for (int i = 1; i <= n; i++){
        d[i] += g[i].size();
        m += g[i].size();
        if (d[i] == 1)
        k.pb(i);
    }
    while(k.size()){
        vector < int > t;
        t.clear();
        for (int v: k){
            int u = *g[v].begin();
            g[u].erase(v);
            if (g[u].size() == 1) t.pb(u);
            g[v].clear();
        }
        k.clear();
        for (int v: t) k.pb(v);
    }
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            r = 0;
            dfs(i);
            if (r == 3) c++;
        }
    }
    m /= 2;
    for (int i = 1; i <= n; i++) s += d[i] * d[i];
    s = s / 2 + m;
    s = n * m - s;
    cout << n * (n - 1) * (n - 2) / 6 - s - c;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED