تقاضای الگوریتم برای مسئله‌ای در مورد گرافها

[Farish]

کسی می‌تونه منو در مورد الگوریتم برای مسئله زیر راهنمایی کنه؟
مسئله اینه که می‌خواهیم تعیین کنیم که در یک گراف آیا دوری وجود دارد که شامل ۲ یال مشخص(که در ورودی داده می‌شود) باشد؟
لینک خود سوال:
http://acm.zju.edu.cn/onlinejudge/sh...problemId=3068
با تشکر

[afi_program]

وقتی داری گراف پیمایش می کنی وقتی به یال مشخص شده رسیدی مثلا به یه شمارنده یکی اضافه کن.زمانی که دور تکمیل شد(شروط بررسی دور چک کن) ببین اگه اون شمارنده 2 بود معلومه هر دو یال بودن.
این کارو تا آخر باید انجام بدی تا تمام دورها بررسی شده باشن.
امیدوارم مشکل حل شده باشه

[Farish]

متاسفانه مشکل این روش اینه که زمان زیادی می‌بره و من خطای Time Limit Exceeded می‌گیرم.

[tdkhakpur]

خوب از توابع بازگشتی کمک بگیرید.
اگر موضوع کارتان را بهتر توضیح بدید میتوان بهتر به نتیجه رسید.

[Farish]

لینک سوال رو در پستم گذاشتم.

[tdkhakpur]

سلام
با کدام زبان؟به خاطر ارسال کد.....

[Farish]

اگر جاوا یا ++C باشه که من بفهمم خب خیلی خوبه.
کدی که من خودم نوشتم و accept نشد رو هم این‌جا می‌ذارم شاید به درد بخوره...

<CODE>
#include <iostream>
#include <vector>
using namespace std;
void preprocess();
void read_input();
bool f(int source);

bool e[1001][1001];
bool marked[1001];
vector<int> neighbour[1001];
int N;
int M;
int x;
int y;
int z;
int w;
int main(){
int T;
cin>>T;
for(int i=0;i<T;i++){
cin>>N>>M;
preprocess();
read_input();
//masir az x be y mikhahim peyda konim ke z,w poshte sare ham bashand dar an
marked[x]=true;
bool b=f(x);
if(b==true){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
//dest y mibashad
bool f(int source){
if(source==y){
if(marked[z]==true && marked[w]==true){
return true;
}
return false;
}
if(source==z && marked[w]==false){
marked[w]=true;

bool b=f(w);
if(b==true){
return true;
}
marked[w]=false;

return false;
}
if(source==w && marked[z]==false){
marked[z]=true;

bool b=f(z);
if(b==true){
return true;
}
marked[z]=false;

return false;
}

vector<int> v=neighbour[source];
for(int i=0;i<v.size();i++){
int t=v[i];
if(e[source][t]==true){
if(marked[t]==false){
marked[t]=true;
bool b=f(t);
if(b==true){
return true;
}
marked[t]=false;
}
}
}


return false;
}
void read_input(){
int s,t;
for(int i=0;i<M;i++){
cin>>s>>t;
e[s][t]=true;
e[t][s]=true;
neighbour[s].push_back(t);
neighbour[t].push_back(s);
}
cin>>x>>y>>z>>w;
e[x][y]=false;
e[y][x]=false;
int F;
cin>>F;
for(int i=0;i<F;i++){
cin>>s>>t;
e[s][t]=false;
e[t][s]=false;
}
}
void preprocess(){
for(int i=1;i<N+1;i++){
marked[i]=false;
neighbour[i].clear();
}
}
</CODE>

[tdkhakpur]

سلام
الگوریتم با بالاترین سرعت در گردش یالها.

 

typedef struct st_

{

  char *Top;

  char *Left;

  char *Right;

  bool Active;

} Graph;

Graph *yal1, *yal2;

int   c = 0;

void FindSameYal( Graph *Next )

{

  if( Next == NULL ) return;

  if( Next == yal1 || Next == yal2 ) C++‎;

  if(c==3){

   cput<<"\n"<<"Finded.";

   c = 0;

  }

  if( !Next->Active ){

   Next->Active = false

   FindSameYal( Next->Left );

   FindSameYal( Next->Right );

   FindSameYal( Next->Top );

   Next->Active = false

  }

}

int main()

{

 Graph graph={0};

 cin >> yal1>>yal2;

//در بالا فرض بر آن میشود که شما گراف را تشکیل داده اید. 

 FindSameYal( &graph )

 return 0;

}