CODEWITHSUNDEEP
c++algorithmtime-complexitycomplexity-theorygraph-algorithm
know dont
know dont

Reputation: 179

DFS and lexicographic path in directed graph?

For example: We have N=4 and M=4 and E={{1,4},{4,2},{1,2},{2,3}}, s=1 and t=3. So the answer is 1->2->3.

This is my attemp: I used DFS-Algorithm to list all path from s to t. And add them into vector<vector>. Then, I sort it and print the first path. But I got TLE.

Now, I don't know how to optimize this problem, can you help me this stuck

This is my code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn (ll)(1e5+5)
#define pb push_back
vector<ll> adj[maxn];
vector<vector<ll>> poi;
vector<ll> really;
ll n,m,i,j,s,d,u,v;
void candy(vector<ll> yui){
   poi.push_back(yui);
   for(i=0;i<poi[0].size();i++) cout<<poi[0][i]+1<<" ";
   exit(0);

}
void aka(ll u, ll d, bool visited[], ll path[], ll &path_index){
   visited[u]=true;
   path[path_index]=u;
   path_index++;
   if(u==d){
      really.clear();
      for(ll i=0;i<path_index;i++)
      really.push_back(path[i]);
      candy(really);
      return ;
   }
   else{
    sort(adj[u].begin(),adj[u].end());
    for(ll i=0;i<adj[u].size();i++)
        if(!visited[adj[u][i]]) aka(adj[u][i],d,visited,path,path_index);
   }
   path_index--;
   visited[u]=false;
}
void solve(ll s, ll d){
   bool visited[maxn];
   ll path[maxn];
   ll path_index = 0;
   for(ll i=0;i<n;i++) visited[i]=false;
   aka(s,d,visited,path,path_index);
}
int main(){
     ios_base::sync_with_stdio(false);

 cin.tie(NULL);

 cout.tie(NULL);
    cin>>n>>m>>s>>d;
    s--;
    d--;
    while(m--){
        cin>>u>>v;
        u--;v--;
        adj[u].pb(v);
    }
    solve(s,d);
   
}

Upvotes: 0

Views: 978

Answers (1)

mangusta
mangusta

Reputation: 3554

Instead of getting all paths from s to t, you may try the following:
On every DFS call, assuming current node is n, get all undiscovered neighbors of n, sort them in increasing order and recursively call them starting from the smallest one.
Note that there is no need to reset visited status prior to returning because the very first found path from s to t is the one we need (so we don't need to inspect any other paths)

Two base cases to consider:

  1. one of neighbors of n is t
  2. n has no undiscovered neighbors

Time complexity is O(V * VlogV + E)

Upvotes: 1

Related Questions