题意:输入一个有向图,判断该图是否是有向无环图(Directed Acyclic Graph)。
解法:还是深搜
1 #include<iostream> 2 #include<memory.h> 3 #include<stack> 4 5 using namespace std; 6 7 bool paths[101][101]; 8 int visited[101]; 9 bool isDAG; 10 int vertices,edges; 11 12 void DFS(int current){ 13 for(int j =1; isDAG == true && j <=vertices; j++){ 14 if(paths[current][j] == true){ 15 if(visited[j] == 0){ 16 visited[j] = 1; 17 DFS(j); 18 } 19 else if(visited[j] == 1) 20 isDAG = false; 21 } 22 } 23 //marked node as visted one stoping duplicated visiting when other visit trying to visit this pre-visit node 24 visited[current] = -1; 25 } 26 int main(){ 27 int from,dest; 28 memset(paths,false,sizeof(paths)); 29 memset(visited,0,sizeof(visited)); 30 cin >> vertices >> edges; 31 for(int i=1;i<= edges;i++){ 32 cin >> from >> dest; 33 paths[from][dest] = true; 34 } 35 //depth-first search checking every node 36 isDAG = true; 37 for(int i=1; isDAG == true && i <= vertices; i++){ 38 if(visited[i] == 0){ 39 visited[i] == 1; 40 DFS(i); 41 } 42 } 43 if(isDAG) 44 cout << 1 << endl; 45 else 46 cout << 0 << endl; 47 return 0; 48 }