SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <cstring>
  5. #include <set>
  6. #include <list>
  7. #include <vector>
  8. #include <algorithm>
  9. using namespace std;
  10. enum Colour {
  11.     White, Gray, Black
  12. };
  13. class Graph {
  14.     int vertexes;
  15.     list<int>* adj;
  16.     bool DFSUtil(int vertex, int colour[]) {
  17.         colour[vertex] = Gray;
  18.         list<int>::iterator it;
  19.         for (it = adj[vertex].begin(); it != adj[vertex].end(); it++) {
  20.             if (colour[*it] == Gray) {
  21.                 return true;
  22.             }
  23.             if (colour[*it] == White && DFSUtil(*it, colour)) {
  24.                 return true;
  25.             }
  26.         }
  27.         colour[vertex] = Black;
  28.         return false;
  29.     }
  30. public:
  31.     Graph(int v) {
  32.         vertexes = v;
  33.         adj = new list<int>[v + 1];
  34.     }
  35.     void addEdge(int from, int to) {
  36.         adj[from].push_back(to);
  37.     }
  38.     bool isCyclic() {
  39.         int* colour = new int[vertexes + 1];
  40.         for (int i = 0; i <= vertexes; i++) {
  41.             colour[i] = White;
  42.         }
  43.         for (int i = 0; i < adj->size(); i++) {
  44.             if (colour[i] == White) {
  45.                 if (DFSUtil(i, colour) == true) {
  46.                     return true;
  47.                 }
  48.             }
  49.         }
  50.         return false;
  51.     }
  52. };
  53. int main() {
  54.     int queries;
  55.     cin >> queries;
  56.     for (int i = 0; i < queries; i++) {
  57.         int vertexes, edges;
  58.         cin >> vertexes >> edges;
  59.         Graph* current = new Graph(vertexes);
  60.         for (int j = 0; j < edges; j++) {
  61.             int from, to, weight;
  62.             cin >> from >> to >> weight;
  63.             current->addEdge(from, to);
  64.         }
  65.         if (current->isCyclic()) {
  66.             cout << "true"<<" ";
  67.         }
  68.         else {
  69.             cout << "false" << " ";
  70.         }
  71.     }
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top