Advertisement
STANAANDREY

check cyc

Feb 5th, 2021
921
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. #define NMAX 103
  4. #define PARTIAL 1
  5. #define COMPLETED 2
  6. bool adjm[NMAX][NMAX];
  7. int cycles[NMAX][NMAX], cycleNr;
  8. int n, m, color[NMAX], daddy[NMAX], pre[NMAX];
  9.  
  10. void read() {
  11.     cin >> n >> m;
  12.     for (int a, b, i = 0; i < m; i++) {
  13.         cin >> a >> b;
  14.         adjm[a][b] = adjm[b][a] = true;
  15.     }
  16. }
  17.  
  18. void dfs(int node, int last) {
  19.     if (color[node] == COMPLETED) {
  20.         return;
  21.     }
  22.     if (color[node] == PARTIAL) {
  23.         cycleNr++;
  24.         int currNode = last;
  25.         cycles[cycleNr][++cycles[cycleNr][0]] = currNode;
  26.         while (currNode != node) {
  27.             currNode = pre[currNode];
  28.             cycles[cycleNr][++cycles[cycleNr][0]] = currNode;
  29.         }
  30.         cout << endl;
  31.         return;
  32.     }
  33.     pre[node] = last;
  34.     color[node] = PARTIAL;
  35.     for (int to = 1; to <= n; to++) {
  36.         if (adjm[node][to] && to != last) {
  37.             dfs(to, node);
  38.         }
  39.     }
  40.     color[node] = COMPLETED;
  41. }
  42.  
  43. void display() {
  44.     if (!cycleNr) {
  45.         puts("Acyclic!");
  46.     }
  47.     for (int i = 1; i <= cycleNr; i++) {
  48.         cout << "cycle num. " << i << ": ";
  49.         bool fr[NMAX] = {}, elementary = true;
  50.         for (int j = 1; j <= *cycles[i]; j++) {
  51.             cout << cycles[i][j] << ' ';
  52.             elementary = elementary && !fr[cycles[i][j]];
  53.             fr[cycles[i][j]] = true;
  54.         }
  55.         if (elementary)
  56.             puts("-elementary");
  57.         else
  58.             puts("-neelementary");
  59.     }
  60. }
  61.  
  62. int main() {
  63.     read();
  64.     for (int i = 1; i <= n; i++)
  65.         dfs(i, -1);
  66.     display();
  67.     return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement