Question: we are given a graph with some edges non directed. we have to find the direction of those edges such that the graph remains acyclic.

My approach: we have to find the ordering of the visit for each node (topological order). This should be the order for the remaining order as well.

Problem: The below solution is getting TLE. I am not sure where it's failing. the complexity should be the order of the number of nodes in the graph.

Thank you!

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
using namespace std;

vector<vector<int>> adj;
vector<int> order;
vector<bool> visited;

void dfs(int u){
    for(int v : adj[u]){
        if(!visited[v]){
            visited[v] = true;
            dfs(v);
        }
    }
    order.push_back(u);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while(t--){
        order.clear();
        adj.assign(200001, vector<int>());
        visited.assign(200001,false);
        int n, m; cin >> n >> m;
        int dir, u, v;
        vector<vector<int>> edges;
        for(int i=0;i<m;++i){
            cin >> dir >> u >> v;
            if(dir) adj[u].push_back(v);
            edges.push_back(vector<int>({dir,u,v}));
        }
        for(int i=1;i<=n;++i){
            if(!visited[i]){
                visited[i] = true;
                dfs(i);
            }
        }
        reverse(order.begin(), order.end());
        vector<int> index(n+1);
        for(int i=0;i<order.size();++i) index[order[i]] = i; 
        bool possible = true;
        // for(int i:order) cout << i << ' ';
        // cout << '\n';
        for(vector<int> i : edges){
            int dir = i[0];
            int u = i[1];
            int v = i[2];
            if(dir && index[u] > index[v]){
                cout << "NO\n";
                possible = false;
                break;
            }
        }

        if(possible){
            cout << "YES\n";
            for(int i=0;i<edges.size();++i){
                int dir = edges[i][0];
                int u = edges[i][1];
                int v = edges[i][2];
                if(!dir){
                    if(index[u] < index[v]){
                        cout << u << ' ' << v << '\n';
                    }
                    else{
                        cout << v << ' ' << u << '\n';
                    }
                }
                else{
                    cout << u << ' ' << v << '\n';
                }
            }
        }
    }
    return 0;
}