已知RE原因:数组开小

求问,那个(些)数组开小?

// 环(circle)
#include <iostream>
#include <vector>
using namespace std;

#define N 200000
int n, m, head, tail, ans;
pair<int, int> q[N * 6];
int dfn[N], low[N], idx, stk[N], tp, scc[N], siz[N], cnt;
bool is_stk[N], is_vis[N][3];
vector<int> e[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++tp] = u;
    is_stk[u] = 1;
    for (int v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (is_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int v;
        ++cnt;
        do {
            v = stk[tp--];
            scc[v] = cnt;
            siz[cnt]++;
            is_stk[v] = 0;
        } while (u != v);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; ++i) {
        if (is_vis[i][0] | is_vis[i][1] | is_vis[i][2]) continue;
        head = 1;
        q[tail = 1] = {i, 0};
        while (head <= tail) {
            int u = q[head].first, mod = q[head].second;
            ++head;
            is_vis[u][mod] = 1;
            for (int v : e[u]) {
                if (scc[v] != scc[u] || is_vis[v][(mod + 1) % 3]) continue;
                q[++tail] = {v, (mod + 1) % 3};
            }
        }
        if (is_vis[i][1]) ans += siz[scc[i]];
    }
    printf("%d\n", ans);
    return 0;
}

2 条评论

  • 1

信息

ID
2772
时间
ms
内存
MiB
难度
6
标签
(无)
递交数
41
已通过
8
上传者