i solved this question but i get timelimit on one test case . please tell me better approach.
Siddharth and Permutations (time limit)
Please share your code so that it will be easy for us to get an insight of what approach have you used and suggest improvements based on your approach.
#include<bits/stdc++.h>
#define ll long long int
#define MAX 1000000
#define p(n) pair<n,n>
#define MOD 1000000007
const int N = 1e5 + 5;
const bool testCase = 0;
using namespace std;
int arr[501];
int n,dn;
vector adj[501];
vector < pair<int, int> > indegree;
vector start;
void fun() {
for (auto it : adj) {
for (auto it2 : it) {
if (it2 == INT_MAX) continue;
indegree[it2].first++;
indegree[it2].second = it2;
}
}
}
bool helper(int small,int big) {
if (big==INT_MAX) {
if (dn == arr[small]) {
–dn;
return true;
}
return false;;
}
if (arr[small]<arr[big]) {
for (auto it2 : adj[big]) {
return helper(big, it2);
}
}
else {
return false;
}
}
bool check() {
vector visited(501,false);
int ct = 0;
dn = n;
for (auto it :start) {
for (auto it2 : adj[it]) {
if (helper(it, it2))
ct++;
}
}
dn = n;
if (ct == start.size()) return true;
else
{
return false;
}
}
bool parmutation(int i,int n) {
if (i > n) {
return check();
/*for (int y = 1;y<= n;y++) {
cout << arr[y] << " ";
}
cout << endl;
return false;*/
}
else {
for (int j = i;j <= n;j++){
swap(arr[i], arr[j]);
if (parmutation(i + 1, n)) {
return true;
}
else {
swap(arr[i], arr[j]);
}
}
}
return false;
}
int main() {
ll t = 1;
if (testCase) {
cin >> t;
}
while (t-- > 0)
{
cin >> n;
dn = n;
indegree.push_back({ 0,0 });
for (int i = 1;i <= n;i++) {
indegree.push_back({0,i});
int t;
cin >> t;
arr[i] = i;
if (t == -1) t = INT_MAX;
adj[i].push_back(t);
}
fun();
sort(indegree.begin(),indegree.end());
for (auto i : indegree) {
if (i.first == 0 ) {
if(i.second != 0)
start.push_back(i.second);
}
else {
break;
}
}
if (parmutation(1,n)) {
for (int i = 1;i <= n;i++) {
cout << arr[i] << " ";
}
}
}
return 0;
}
// First i create all permutation and check one by one if that is satisfy the the graph condition(it is create using given array.)or not.
If you check for all permutations, then it will give TLE, please think of an optimized approach.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
i tried to use topological sort but i m not able to proceed further. can u please tell how we can use topological sort here