تشخیص دو بخشی بودن گراف

[fatemegm]

قبلن این سوال (85)جواب دادن ولی به نظرم اشتباهه
می شه خیلی سریع یکی جواب بده من همین الان جوابو لازم دارم

[qwerty11]

سلام !
از جستجوی اول سطح یا اول عمق میتونی استفاده کنی !

به یکی از گره ها رنگ سفید نسبت بده، پس به فرزنداش باید رنگ سیاه نسبت داده بشه و به همین ترتیب ... تو هر مرحله اگر رنگ 2 تا راس که با یه یال به هم وصل هستن یکی بود در این صورت گراف دو بخشی نیست ! سودو کدش اینجوریه مثلاً : من با جستجوی اول عمق نوشتم.

boolean isBipartite(){

 for(i=0; i<n; i++){

  if(!mark[i]){

   color i = WHITE

   if(!dfs(i)) return false

  }

 }

 return true;

}

boolean dfs(int i){

 mark[i]=true

 for each node x in e[i] {

  if(i & x have same color) return false

  color x = symmetry color i

  if(!mark[i]) if(!dfs(i)) return false

 }

 return true

}