#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