【数据结构】SJTU OJ 1237

http://acm.sjtu.edu.cn/OnlineJudge/problem/1237

烦死了烦死了

应该按照年份考虑的，自己做的时候又忘记减入度，真是活该。快复习！！

#include <iostream>

using namespace std;
int begin=1,tail=0,Q[100001]={0},cnt=0,tmp=0,res=0,de;
int begin_=1,tail_=0,Q_[100001]={0};
void enQueue_(int x)
{
    ++tail_;
    Q_[tail_]=x;
}
int result[101];
void enQueue(int x)
{
    ++tail;
    Q[tail]=x;
}
class graph
{
private:
    int vSize,eSize;
    struct edgeNode{
        int weight;
        int end;
        edgeNode*next;
        edgeNode(int e,int w,edgeNode *n=NULL)
        {
            weight=w;
            end = e;
            next=n;
        }
    };
    struct verNode{
        int ver;
        edgeNode*head;
        verNode(edgeNode*h=NULL)
        {
            head = h;
        }
    };
    verNode*verList;
public:
    graph(int size)
    {
        vSize =size;
        eSize =0;
        verList = new verNode[vSize+1];
        for(int i=1;i<=vSize;++i)
        {
            verList[i].ver =i;
        }
    }
    void insert(int u,int v,int weight=1)
    {
        verList[u].head = new edgeNode(v,weight,verList[u].head);
        eSize++;
    }
    int topSort()
    {
        int *inDegrees=new int[vSize+1];
        for(int i=1;i<=vSize;++i)
            inDegrees[i]=0;
        for(int i=1;i<=vSize;++i)
        {
            edgeNode*p=verList[i].head;
            while(p!=NULL)
            {
                ++inDegrees[p->end];
                p=p->next;
            }
        }
        bool *marked=new bool[vSize+1];for(int j=1;j<=vSize;++j) marked[j]=false;
        for(int i=1;i<=vSize;++i)
        {
            if(inDegrees[i]==0)
            {
                enQueue(i);
            }
        }

        while(begin<=tail)
        {
            if(begin<=tail)++tmp;
            while(begin<=tail)
            {
                de =Q[begin];begin++;
                marked[de]=true;
                edgeNode*p=verList[de].head;
                while(p!=NULL){
                    if(marked[p->end]==false)
                    {
                        if(--inDegrees[p->end]==0)enQueue_(p->end);
                    }
                    p=p->next;
                }
            }
        if(begin_<=tail_) tmp++;
        while(begin_<=tail_)
        {
            de = Q_[begin_];begin_++;
            marked[de]=true;
            edgeNode*p=verList[de].head;
            while(p!=NULL){
                if(marked[p->end]==false)
                {
                   if(--inDegrees[p->end]==0) enQueue(p->end);
                  //  marked[p->end]=true;
                }
                p=p->next;
            }
        }
        }
        return tmp;
    }
};
int main()
{
    int n,m,u,v;
    cin>>n>>m;
    graph g(n);
    for(int i=0;i<m;++i)
    {
        cin>>u>>v;
        g.insert(u,v);
    }
    g.topSort();
    cout<<tmp;
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!