uva 11504 Dominos动态分配内存

这题是给定许多骨牌，以及相对应的关系， a->b 就表示a 倒之后会推倒 b

题目要求说最少推倒几个就可以使骨牌全部倒!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

#define Max  100009
#define max(a,b) a>b?a:b

struct node{
    int u,v,next;
}*Edge;

stack<int> S;

int k,Dindex,Stop,Bcnt,n,m;
int head[Max],DFN[Max],LOW[Max],Belong[Max];
int in[Max];
bool instack[Max];

void add(int u,int v){
    Edge[k].u = u;
    Edge[k].v = v;
    Edge[k].next = head[u];
    head[u] = k++;
}

void tarjan(int i)
{
    int j;
    DFN[i]=LOW[i]=++Dindex;
    instack[i]=true;
    S.push(i);
    for (int w=head[i];w!=-1;w=Edge[w].next)
    {
        j=Edge[w].v;
        if (!DFN[j])
        {
            tarjan(j);
            if (LOW[j]<LOW[i])
                LOW[i]=LOW[j];
        }
        else if (instack[j] && DFN[j]<LOW[i])
            LOW[i]=DFN[j];
    }
    if (DFN[i]==LOW[i])
    {
        Bcnt++;
        do
        {
            j=S.top();
            S.pop();
            instack[j]=false;
            Belong[j]=Bcnt;
        }
        while (j!=i);
    }
}

void init() {
    while(!S.empty())
        S.pop();
    memset(head,-1,sizeof(head));
    memset(DFN,0,sizeof(DFN));
    memset(in,0,sizeof(in));
    k=Dindex=Stop=Bcnt=0;
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        Edge = new node[m+5];
        init();
        for(int i=0;i<m;i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        for(int i=1;i<=n;i++) {
            if(!DFN[i])
                tarjan(i);
        }
        for(int i=0;i<k;i++) {
            int s = Belong[Edge[i].u];
            int e = Belong[Edge[i].v];
            if(s != e)
                in[e]++;
        }
        int ans = 0;
        for(int i=1;i<=Bcnt;i++) {
            if(in[i] == 0)
                ans++;
        }
        printf("%d\n",ans);
        delete[] Edge;
    }
    return 0;
}

不动态分配内存会RE，无解的RE!!!

关于系统内存分配的资料

http://blog.csdn.net/netgeek/article/details/1817311