#include<bits/stdc++.h>
#define White 1
#define Gray 2
#define Black 3
#define N 10020
using namespace std;
int a[N][N], c[N], s[N], f[N], t = 1, node, edge;
stack<int>st;
void dfsvisit(int x)
{
c[x] = Gray;
s[x] = t;
t++;
for(int i=1;i<=node;i++)
{
if(a[x][i] == 1)
{
if(c[i] == White)
dfsvisit(i);
}
}
c[x] = Black;
f[x] = t;
t++;
st.push(x);
}
void dfs()
{
for(int i=1;i<=node;i++)
{
c[i] = White;
}
for(int i=1;i<=node;i++)
{
if(c[i] == White)
dfsvisit(i);
}
}
int main()
{
int n1, n2;
cout << "Enter Node Number :: ";
cin >> node;
cout << "Enter Edge Number :: ";
cin >> edge;
cout << "\nEnter Edges :: \n";
for(int i=1;i<=edge;i++)
{
cin >> n1 >> n2;
a[n1][n2] = 1;
}
dfs();
cout << "Topological Sort Order :: ";
while(!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << "\n";
return 0;
}
#define White 1
#define Gray 2
#define Black 3
#define N 10020
using namespace std;
int a[N][N], c[N], s[N], f[N], t = 1, node, edge;
stack<int>st;
void dfsvisit(int x)
{
c[x] = Gray;
s[x] = t;
t++;
for(int i=1;i<=node;i++)
{
if(a[x][i] == 1)
{
if(c[i] == White)
dfsvisit(i);
}
}
c[x] = Black;
f[x] = t;
t++;
st.push(x);
}
void dfs()
{
for(int i=1;i<=node;i++)
{
c[i] = White;
}
for(int i=1;i<=node;i++)
{
if(c[i] == White)
dfsvisit(i);
}
}
int main()
{
int n1, n2;
cout << "Enter Node Number :: ";
cin >> node;
cout << "Enter Edge Number :: ";
cin >> edge;
cout << "\nEnter Edges :: \n";
for(int i=1;i<=edge;i++)
{
cin >> n1 >> n2;
a[n1][n2] = 1;
}
dfs();
cout << "Topological Sort Order :: ";
while(!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << "\n";
return 0;
}
Comments
Post a Comment