這是一道圖的題目
單向圖 并且沒(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;
}