指针链式前向星 90pts, Task #19,20 MLE, 求教

指针写的链式前向星，看上去可能有些另类。。。

手算了一下内存，不应该超的。不知怎么就 MLE 了。求教。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>

#include <vector>
#include <algorithm>

template <class T>
inline T readint() {
    T ret = 0; int ch = getchar(); bool negative = false;
    while (ch < '0' || ch > '9') { if (ch == '-') negative = true; if (ch == EOF) return EOF; ch = getchar(); }
    while (ch >= '0' && ch <= '9') ret = (ret << 1) + (ret << 3) + ch - 48, ch = getchar();
    return negative ? -ret : ret;
}

#define NAMESPACE_BEGIN(ns) namespace ns {
#define NAMESPACE_END       }

NAMESPACE_BEGIN(graph)

struct Edge { int to; bool bridge; Edge* next; Edge* inv; };

Edge* createEdge(int to, Edge* next) {
    Edge* e = new Edge;
    e->to = to, e->bridge = false, e->next = next, e->inv = nullptr;
    return e;
}

struct Graph { int ver; Edge** edge; };

Graph* createGraph(int ver) {
    Graph* g = new Graph;
    g->ver = ver, g->edge = new Edge*[ver + 1];
    memset(g->edge, 0, sizeof(Edge*) * (ver + 1));
    return g;
}

inline void addEdgeUndirected(Graph* g, int u, int v) {
    g->edge[u] = createEdge(v, g->edge[u]);
    g->edge[v] = createEdge(u, g->edge[v]);
    g->edge[u]->inv = g->edge[v];
    g->edge[v]->inv = g->edge[u];
}

NAMESPACE_BEGIN(dcc)

struct DCCInfo {
    Graph* g;
    int timestamp; int* rank; int* low;
    int cntedcc; int* edcc; std::vector<int>* contain;
};

DCCInfo* create(Graph* g) {
    DCCInfo* dcc = new DCCInfo;
    dcc->g = g, dcc->timestamp = dcc->cntedcc = 0;
    dcc->rank = new int[g->ver + 1];
    dcc->low = new int[g->ver + 1];
    dcc->edcc = new int[g->ver + 1];
    memset(dcc->rank, -1, sizeof(int) * (g->ver + 1));
    memset(dcc->edcc, -1, sizeof(int) * (g->ver + 1));
    return dcc;
}

void tarjan(DCCInfo* dcc, int p, Edge* ecur) {
    dcc->rank[p] = dcc->low[p] = ++dcc->timestamp;

    for (Edge* e = dcc->g->edge[p]; e; e = e->next)
        if (dcc->rank[e->to] == -1) {
            tarjan(dcc, e->to, e);
            dcc->low[p] = std::min(dcc->low[p], dcc->low[e->to]);
            if (dcc->low[e->to] > dcc->rank[p])
                e->bridge = e->inv->bridge = true;
        } else if (!ecur || e != ecur->inv)
            dcc->low[p] = std::min(dcc->low[p], dcc->rank[e->to]);
}

void fill(DCCInfo* dcc, int p, int edcc) {
    dcc->edcc[p] = edcc;
    for (Edge* e = dcc->g->edge[p]; e; e = e->next)
        if (dcc->edcc[e->to] == -1 && !e->bridge)
            fill(dcc, e->to, edcc);
}

void exec_tarjan(DCCInfo* dcc) {
    for (int p = 1; p <= dcc->g->ver; ++p)
        if (dcc->rank[p] == -1) 
            tarjan(dcc, p, nullptr);

    delete[] dcc->rank;
    delete[] dcc->low;
    for (int p = 1; p <= dcc->g->ver; ++p)
        if (dcc->edcc[p] == -1)
            fill(dcc, p, ++dcc->cntedcc);

    dcc->contain = new std::vector<int>[dcc->cntedcc + 1];
    for (int p = 1; p <= dcc->g->ver; ++p)
        dcc->contain[dcc->edcc[p]].push_back(p);
    delete[] dcc->edcc;
}

NAMESPACE_END

NAMESPACE_END

int main(int argc, char *argv[]) {
    int nver = readint<int>();
    int nedge = readint<int>();

    graph::Graph* g = graph::createGraph(nver);
    for (int e = 0, u, v; e < nedge; ++e) {
        u = readint<int>();
        v = readint<int>();
        graph::addEdgeUndirected(g, u, v);
    }

    graph::dcc::DCCInfo* dcc = graph::dcc::create(g);
    graph::dcc::exec_tarjan(dcc);

    printf("%d\n", dcc->cntedcc);
    for (int c = 1; c <= dcc->cntedcc; ++c) {
        printf("%d ", dcc->contain[c].size());
        for (auto it = dcc->contain[c].begin(); it != dcc->contain[c].end(); ++it)
            printf("%d%c", *it, " \n"[it == --dcc->contain[c].end()]);
    }

    delete[] dcc->contain;

    return 0;
}