Thursday, 19 February 2026

Tpoplogical sort uncompleted

 #include<bits/stdc++.h>


using namespace std;


class Graph {


vector<vector<int>>adj;


int v;


public:


void no_node(int n) {


v = n;


adj.resize(n);


}


void addEdge(int i,int j) {


adj[i].push_back(j);


// adj[j].push_back(i);


}


void show() {


for(int i=0; i<v; i++) {


for(int j=0; j<adj[i].size(); j++) {


cout<<adj[i][j]<<" ";


}


cout<<endl;


}


}


bool Dc_DFS(int node,vector<vector<int>>&edges,int parent,vector<int>&v){


        if(!v[node])v[node] = 1;


        else return 1;


        for(int i=0;i<edges[node].size();i++){


            if(edges[node][i]==parent) continue;


            if(Dc_DFS(edges[node][i],edges,node,v)){


                return 1;


            }


        }


        return 0;


    }


void Check_Cycle_DFS(){


    vector<int>visited(v,0);


    if(Dc_DFS(0,adj,-2,visited)){


        cout<<"cycle exists";


    }


    cout<<endl;


}


void Check_Cycle_BFS(){


    vector<int>visited(v,0);


    queue<pair<int,int>>q;


    q.push({-1,0});


    visited[0]=1;


    while(!q.empty()){


        auto  x=q.front();


        int item=x.second;


        int p=x.first;


        q.pop();


        for(int i:adj[item]){


            if(i==p) continue;


            if(visited[i]){


                cout<<"there is cycle";


                return;


            }


            else{


                q.push({item,i});


                visited[i]=1;


            }


        }


    }


}

void sorting(int node,stack<int>&st,vector<int>&v,vector<vector<int>>&adj){

    v[node]=1;

    for(int x:adj[node]){

        if(!v[x])sorting(x,st,v,adj);

    }

    st.push(node);

}

void Topological_sort(){

     stack<int>st;

     vector<int>V(v,0);

     sorting(0,st,V,adj);

     while(!st.empty()){

      cout<<st.top()<<" ";

      st.pop();

}

     

     

   

 }


};


int main() {


Graph g;


g.no_node(4);


g.addEdge(0,1);


g.addEdge(0,2);

g.addEdge(1,3);

g.addEdge(2,3);




g.show();


// g.Check_Cycle_DFS();


// g.Check_Cycle_BFS();

    g.Topological_sort();



}

No comments:

Post a Comment

SDE floyd-warshall algorithm

 // User function template for C++ class Solution {   public:     void floydWarshall(vector<vector<int>> &dist) {         //...