http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net
Здраво, дали ќе може некоја идеја како да го подобрам решението? Јавува точен резултат само за првите 4 тест примери, а другите се надминат временски лимит.
Еве го мојот код:

[code]#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;

vector <long long> G[300001];

int DFS(int start)
{
int visited[300001];
memset(visited,0,sizeof(visited));

stack<int>st;
st.push(start);

while(true)
{
int node=st.top();
st.pop();
visited[node]=1;
//vidi dali za nego e nula odnosno ne izleguva strelka
if(G[node][0]==0)
{
//tuka zavrsuva;
return node;
}
else if(visited[G[node][0]]!=0)
{
//ciklus
return -1;
}
else
{
st.push(G[node][0]);
}
}
}


int main()
{
long long n;
cin>>n;

for(long long i=1; i<=n; i++)
{
long long a;
cin>>a;
G[i].push_back(a);
}
long long n2;
cin>>n2;
for(long long i=0; i<n2; i++)
{
long long prasanka,broj;
cin>>prasanka>>broj;
if(prasanka==1)
{
long long rez=DFS(broj);
if(rez==-1)
{
cout<<"CIKLUS"<<endl;
}
else
{
cout<<rez<<endl;
}
}
else
{
G[broj][0]=0;
}
}
return 0;
}[/code]
]]> http://mendo.mk/jforum/posts/preList/692/3777.page http://mendo.mk/jforum/posts/preList/692/3777.page GMT http://mendo.mk/jforum/posts/preList/692/3782.page http://mendo.mk/jforum/posts/preList/692/3782.page GMT
Здраво, дали ќе може некоја идеја како да го подобрам решението? Јавува точен резултат само за првите 4 тест примери, а другите се надминат временски лимит.[/quote]

Хинт 1: Можеби можеш да ги прочиташ сите прашанки на почетокот, и потоа да ги разгледуваш во обратен редослед. Тогаш, наместо да бришеме стрелки, ќе додаваме стрелки.]]> http://mendo.mk/jforum/posts/preList/692/3785.page http://mendo.mk/jforum/posts/preList/692/3785.page GMT