題目地址

這是一道圖的題目
單向圖 并且沒(méi)有環(huán)(只能向西走 保證了沒(méi)有環(huán))
這題目要求計(jì)算出每個(gè)節(jié)點(diǎn)離最東邊點(diǎn)的最長(zhǎng)路徑
用拓?fù)渑判?完成對(duì)圖的遍歷
在遍歷過(guò)程完成dp 得到結(jié)果

拓?fù)渑判虻牧鞒?br> 先計(jì)算每個(gè)點(diǎn)的入度
然后將入度為0的點(diǎn)寫入隊(duì)列
然后開(kāi)始遍歷入度為0的點(diǎn)
刪除入度為0的點(diǎn) 將與入度為0點(diǎn)的子節(jié)點(diǎn)入度-1
然后將新得到得入度為0得點(diǎn)重新寫入隊(duì)列
繼續(xù)上面得遍歷過(guò)程 直到所有的點(diǎn)入度為0

dp的過(guò)程
用數(shù)組result保存每個(gè)點(diǎn)的結(jié)果
第一批入度為0的點(diǎn)賦值為1
result[i]=max(result[父節(jié)點(diǎn)])+1

#include <stdio.h>

//圖的邊的結(jié)構(gòu)體(也可以用來(lái)表示樹(shù))
struct LinkList
{
    //節(jié)點(diǎn)編號(hào)
    int index;
    //所有連接節(jié)點(diǎn)的邊 包括根節(jié)點(diǎn)
    LinkList* next;
    // LinkList* pre;
};

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//添加單項(xiàng)邊
void addSinglEv(LinkList** ev,int start,int end)
{
    LinkList* l=new LinkList;
    l->index=end;

    if(ev[start]==NULL)
    {
        l->next=NULL;
        ev[start]=l;
    }
    else{
        l->next=ev[start];
        ev[start]=l;
    }
}

struct Queue
{
    int start; //隊(duì)列起點(diǎn)
    int end;   //隊(duì)列終點(diǎn)
    int maxLen;//隊(duì)列最大元素個(gè)數(shù)
    int* data;//隊(duì)列元素
};

Queue* newQueue(int maxLen)
{
    Queue* q=new Queue;
    q->maxLen=maxLen;
    q->data=new int[maxLen];
    q->start=0;
    q->end=0;
    return q;
}

void deleteQueue(Queue* q)
{
    delete q->data;
    delete q;
}

//入隊(duì)
void inqueue(Queue* q,int num){
    q->data[q->end]=num;
    q->end++;
    if(q->end>=q->maxLen)
    {
        q->end=0;
    }
}

//出隊(duì)
int dequeen(Queue* q){
    int num=q->data[q->start];
    q->start++;
    if(q->start>=q->maxLen)
    {
        q->start=0;
    }
    return num;
}

//隊(duì)列元素多少
int sizeOfQueue(Queue* q)
{
    if(q->start==q->end)
    {
        return 0;
    }
    else{
        int len=q->end-q->start;
        if(len>0)
        {
            return len;
        }
        else{
            return len+q->maxLen;
        }
    }
}

//隊(duì)列是否為空
int isEmpQueue(Queue* q)
{
    return q->start==q->end;
}


int main(){
    int n,m;
    int i,j;
    scanf("%d %d",&n,&m);
    int* result=new int[n];

    //儲(chǔ)存節(jié)點(diǎn)入度
    int* input=new int[n];
    //記錄樹(shù)所有頂點(diǎn)
    LinkList** ev=new LinkList*[n];

    for(i=0;i<n;i++)
    {
        input[i]=0;
        result[i]=0;
        ev[i]=NULL;
    }

    int tmp1,tmp2;
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&tmp1,&tmp2);
        tmp1--;
        tmp2--;

        //添加單向邊
        addSinglEv(ev,tmp1,tmp2);
        //入度+1
        input[tmp2]++;
    }

    Queue* q=newQueue(m);
    for(i=0;i<n;i++)
    {
        if(input[i]==0)
        {
            inqueue(q,i);
            result[i]=1;
            input[i]=-1;
        }
    }

    while (!isEmpQueue(q))
    {
        int size=sizeOfQueue(q);
        for(i=0;i<size;i++)
        {   
            //刪除入度為0的節(jié)點(diǎn)
            int index=dequeen(q);
            int value=result[index]+1;
            LinkList* l=ev[index];
            //遍歷子節(jié)點(diǎn)
            while (l!=NULL)
            {
                int newIndex=l->index;
                //計(jì)算子節(jié)點(diǎn)的值
                if(result[newIndex]<value)
                {
                    result[newIndex]=value;
                }

                //子節(jié)點(diǎn)入度-1
                input[newIndex]--;
                //將入度為0的點(diǎn)入隊(duì) 作為下一批的遍歷對(duì)象
                if(input[newIndex]==0)
                {
                    inqueue(q,newIndex);
                    input[newIndex]=-1;
                } 
                l=l->next;
            }
        }
    }
    

    for(i=0;i<n;i++)
    {
        deleteLinkList(ev[i]);
    }
    delete ev;

    deleteQueue(q);

    for(i=0;i<n;i++)
    {
        printf("%d\n",result[i]);
    }
    delete input;
    delete result;
}