学步园

又是离散作业 ，无环图两点间路径数目，不指出具体路径，不判断图是否有环

Write a program that takes as input a directed acyclic graph G = (V, E) and two

vertices s and t, and returns the number of paths from s to t in G.

思路：通过DFS求拓扑排序，利用拓扑排序的有序性，求两点间的所有路径数

void Graph::initDFS(){
 initBFS();
 for(int i=0;i<nodeCounts;i++){
  graNodes[i].fin=INF;
 }
}

bool Graph::DFS(){
 initDFS();
 int time=0;
 for(int i=0;i<nodeCounts;i++){
  if(graNodes[i].color==WHITE)
   DFSVisit(&graNodes[i],&time);
 }
 return true;
}

void Graph::DFSVisit(Node* uNode, int* time){
 uNode->color=GRAY;
 (*time)++;
 uNode->level=(*time);
 for (vector<Node*>::iterator ivl = (uNode->adjList).begin(); ivl != (uNode->adjList).end(); ivl++) {
  if((*ivl)->color==WHITE){
   (*ivl)->pre=uNode->nodeID;
   DFSVisit(*ivl,time);
  }
 }
 uNode->color=BLACK; 
 (*time)++;
 uNode->fin=(*time);
 //cout<<"*"<<uNode->nodeID<<"*"<<uNode->level<<"*"<<uNode->fin<<endl;
}

int Graph::Paths(int s,int t){
 if(s>=nodeCounts || t>=nodeCounts){
  cout<<"输入的节点不在图中"<<endl;
  return 0;
 }

 DFS();

 int sT=graNodes[s].fin;
 //cout<<sT<<endl;
 int tT=graNodes[t].fin;
 //cout<<tT<<endl;
 if(sT<=tT){
  cout<<"终点比起点先结束"<<endl;
  return 0;
 }
  
 for(int i=0;i<nodeCounts;i++){
  graNodes[i].justPaths=JUST;
 }
 graNodes[s].justPaths=1;
 
 deque<Node*> blocks;
 blocks.clear();
 blocks.push_back(&graNodes[s]);
 
 Node* tempNode;
 int time;

 int num=sT-tT;
 int* dequeNode=new int[num];

 for(int i=0;i<num;i++)
  dequeNode[i]=INF;

 for(int i=0;i<nodeCounts;i++){
  time=graNodes[i].fin-tT;
  if(time<num && time>0){
   dequeNode[time]=graNodes[i].nodeID;
  }
 }

 for(int i=num-1;i>0;i--){
  int id=dequeNode[i];
  if(id!=-1){
   blocks.push_back(&graNodes[id]);
  }
 }

 while(!blocks.empty()){
  tempNode=blocks.front();
  //cout<<"xjt"<<tempNode->nodeID<<endl;
  time=tempNode->fin;
  blocks.pop_front();
  for (vector<Node*>::iterator ivl = (tempNode->adjList).begin(); ivl != (tempNode->adjList).end(); ivl++) {
   if((((*ivl)->fin)<time) && (((*ivl)->fin)>=tT)){
    ((*ivl)->justPaths)+=tempNode->justPaths;
   }
   //cout<<(*ivl)->nodeID<<"***"<<(*ivl)->justPaths<<endl; 
  }
 }
   
 return graNodes[t].justPaths;
}