C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Check Cycle in a Graph using Topological Sort Program to Check Cycle in a Graph using Topological Sort This C++ program displays the topological sort method of finding whether a given graph contains cycles or not using Kosaraju's Algorithm. #include<iostream> #include<conio.h> using namespace std; struct node_info { int no; int lv_time, st_time; }*q = NULL; struct node { node_info *pt; node *next; }*top = NULL, *p = NULL, *np = NULL; struct node1 { node1 *link; node_info *pt1; }*head = NULL, *m = NULL, *n = NULL, *np1 = NULL; int c = 0; bool flag = false; void push(node_info *ptr) { np = new node; np->pt = ptr; np->next = NULL; if (top == NULL) { top = np; } else { np->next = top; top = np; } } node_info *pop() { if (top == NULL) { cout<<"underflow\n"; } else { p = top; top = top->next; return(p->pt); delete(p); } } void store(node_info *ptr1) { np1 = new node1; np1->pt1 = ptr1; np1->link = NULL; if (c == 0) { head = np1; m = head; m->link = NULL; c++; } else { m = head; np1->link = m; head = np1; } } void remove(int x) { m = head; if ((m->pt1)->no == x) { head = head->link; delete(m); } else { while ((m->pt1)->no != x && m->link != NULL) { n = m; m = m->link; } if ((m->pt1)->no == x) { n->link = m->link; delete(m); } else if (m->link == NULL) { flag = true; cout<<"Cycles do not exist in graph\n"; } } } void topo(int *v, int am[][5], int i) { q = new node_info; q->no = i; q->st_time = c; push(q); v[i] = 1; for (int j = 0; j < 5; j++) { if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1)) continue; else if(am[i][j] == 1 && v[j] == 0) { c++; topo(v,am,j); } } c++; q = pop(); q->lv_time = c; store(q); return; } void topo1(int *v, int am[][5], int i) { v[i] = 1; remove(i); for (int j = 0; j < 5; j++) { if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1)) { continue; } else if(am[i][j] == 1 && v[j] == 0) { topo1(v, am, j); } } return; } void addEdge(int am[][5], int src, int dest) { am[src][dest] = 1; return; } int main() { int v[5], am[5][5], amt[5][5], c = 0, a, b; for (int i = 0; i < 5; i++) { v[i] = 0; } for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { am[i][j] = 0; } } while (c < 5) { cout<<"Enter the source and destination\n"; cin>>a>>b; addEdge(am, a, b); c++; } topo(v, am, 0); for (int i = 0; i < 5; i++) { v[i] = 0; for (int j = 0; j < 5; j++) { amt[j][i] = am[i][j]; } } if (head != NULL) { topo1(v, amt, (head->pt1)->no); if (flag == false) { cout<<"Cycles exist in graph\n"; } } getch(); }