题意:输入一个有向图,判断该图是否是有向无环图(Directed Acyclic Graph)。
解法:还是深搜
#include<iostream>
#include<memory.h>
#include<stack> using namespace std; bool paths[][];
int visited[];
bool isDAG;
int vertices,edges; void DFS(int current){
for(int j =; isDAG == true && j <=vertices; j++){
if(paths[current][j] == true){
if(visited[j] == ){
visited[j] = ;
DFS(j);
}
else if(visited[j] == )
isDAG = false;
}
}
//marked node as visted one stoping duplicated visiting when other visit trying to visit this pre-visit node
visited[current] = -;
}
int main(){
int from,dest;
memset(paths,false,sizeof(paths));
memset(visited,,sizeof(visited));
cin >> vertices >> edges;
for(int i=;i<= edges;i++){
cin >> from >> dest;
paths[from][dest] = true;
}
//depth-first search checking every node
isDAG = true;
for(int i=; isDAG == true && i <= vertices; i++){
if(visited[i] == ){
visited[i] == ;
DFS(i);
}
}
if(isDAG)
cout << << endl;
else
cout << << endl;
return ;
}