#include?
#include?
#include?
#include?
#include
#include?
using?namespace?std;

/*鏈表節點定義*/
struct?listNode{
????int?name;/*節點號*/
????listNode?*next;

????listNode（int?xlistNode?*t）{
????????name=x;
????????next=t;
????}
};
/*頭節點定義*/
struct?vNode{
????int?color;/*0:白色；1：灰色；2：黑色*/
????int?len;
????int?nextN;//DAG圖最長路徑的后續結點
????int?indeg;
????listNode?*next;
};

const?int?v=100;?/*點數*/
const?int?e=500;?/*邊數*/
int?topoList[v];/*拓撲序列*/
int?topo=0;/*拓撲序列中已有的元素個數*/

class?GraphlinkedTable{
public:
????vNode?vertex[v];/*定義頭結點*/
????vNode?dag[v];

????GraphlinkedTable（）;
????~GraphlinkedTable（）{};
????void?buildGraph（）;
????bool?searchEdge（int?v1int?v2）;
????void?insertEdge（vNode?*nodeint?v1int?v2）;
????void?print（vNode?*v）;
????void?searchBFS（int?v1）;
????int?searchV（int?v1）;/*尋找未被標記的結點*/
????void?DFS（int?v1）;/*第一種遍歷方法*/
????void?InDegeree（）;/*計算每個點的入度*/
????int?DP（int?v1）;
????void?searchLen（）;
????void?printPath（int?v1）;
};
GraphlinkedTable::GraphlinkedTable（）/*構造函數*/
{
????for（int?i=0;i????{
????????vertex[i].next=NULL;
????????vertex[i].color=0;/*0表示還未遍歷過*/
????????vertex[i].len=0;
????????vertex[i].nextN=-1;
????????vertex[i].indeg=0;
????????//vertex[i].dp=0;
????????dag[i].next=NULL;
????}
}
void?GraphlinkedTable::buildGraph（）{}
void?GraphlinkedTable::insertEdge（vNode?*vint?v1int?v2）{
????listNode?*node=（listNode*）malloc（sizeof（listNode*））;
????node->name=v2;
????node->next=NULL;/*構造節點*/

????listNode?*temp=v[v1].next;
????if（!temp）{/*若無其他節點*/
????????v[v1].next=node;
????????return;
????}
????listNode?*tempbefore;
????while（temp）{/*遍歷所有節點*/
????????tempbefore=temp;
????????temp=temp->next;
????}
????tempbefore->next=node;
}
bool?GraphlinkedTable::searchEdge（int?v1int?v2）{
????listNode?*temp=vertex[v1].next;
????int?edge=0;
????while（temp）{
????????if（temp->name==v2）{
????????????edge=1;
????????????break;
????????}
????????temp=temp->next;
????}

????if（edge==0）/*邊不存在返回true否則返回false*/
????????return?true;
????else
????????return?false;
}
void?GraphlinkedTable::print（vNode?*node）{
????for（int?i=0;i????????cout<“;
????????listNode?*temp=node[i].next;
????????while（temp）{
????????????cout<name<<“->“;
????????????temp=temp->next;
????????}
????????cout<<“null“<????}
}
void?GraphlinkedTable::searchBFS（int?v1）{
????int?dis[v];/*初始化距離*/
????for（int?i=0;i????????dis[i]=-1;
????}
????dis[v1]=0;
????int?u;/*前驅結點的值*/
????int?v2;/*當前節點的值*/
????bool?end1=false;/*是否結束循環*/
????while（!end1）{
????????end1=true;
????????queue?q;/*定義一個隊列*/
????????q.push（v1）;/*將源結點加入隊列中*/
????????while（!q.empty（））{
????????????u=q.front（）;
????????????q.pop（）;
????????????listNode?*temp=vertex[u].next;
????????????while（temp）{
????????????????v2=temp->name;
????????????????if（dis[v2]==-1）{/*該結點未被遍歷過*/
????????????????????q.push（v2）;
??????????