Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

สวัสดีครับๆ อันนี้ก็เป็น blog post อันแรกใน ThailandOI ของผม ถ้าอ่านแล้วมีข้อติชมตรงไหนก็โพสต์บอกใน comment ด้วยละกันนะครับ

SCC เป็นอีก algorithm นึงที่มีประโยชน์ในการจัดการกับกราฟ แม้จะพบไม่บ่อยในข้อสอบ แต่ก็ควรจะรู้จักและใช้ให้เป็น ในบทความนี้จะแนะนำ SCC และมี psuedocode ให้ พร้อมทั้งตัวอย่างการเอาไปใช้แก้ปัญหา

SCC คืออะไร?

SCC (Strongly Connected Component) ตามนิยามก็คือกลุ่มของ node ใน directed graph โดยที่ทุก node i,j ใดๆ ในนั้น สามารถไปหากันได้
สามารถอ่านเพิ่มเติมได้จาก บทความ Strongly Connected Component ในวิกิพีเดีย

แล้ว SCC มีไว้ทำอะไร?

เพราะเมื่อเราทำ SCC กับ directed graph (คือการจัดกลุ่ม node เป็น กลุ่มๆ โดยที่แต่ละกลุ่มเป็น SCC ที่มีขนาดใหญ่ที่สุด) และแปลงแต่ละกลุ่มนั้นให้เป็น node เราจะได้ directed acyclic graph (DAG = กราฟมีทิศทางที่ไม่มี cycle) ซึ่งสามารถแก้ปัญหาได้ง่ายกว่า directed graph ธรรมดาที่มี cycle มาก กระบวนการแปลง directed graph ให้กลายเป็น dag เรียกว่า condensation

(ภาพจากวิกิพีเดีย)

จากภาพ มีกราฟอยู่ ในส่วนที่อยู่ในสีเทาเดียวกัน คืออยู่ใน SCC เดียวกัน ซึ่งเมื่อเรา condense กราฟนี้แล้ว จะเหลือแค่ 3 node
คือ , และ และมี edge จาก -> และ ->

ตัวอย่างโจทย์ที่ใช้ SCC

ข้อ The Great ATM Robbery จาก APIO 2009

โหลดได้ที่นี่

สำหรับโจทย์ข้อนี้ มี directed graph ที่แต่ละ node มีเงินอยู่ กำหนดจุดเริ่มต้น และ จุดจบที่เป็นไปได้ (มีหลายจุด) จะเดินอย่างไรให้เริ่มจากจุดเริ่มต้นนั้น และจบในจุดจบใดๆ ที่มีให้ แล้วเก็บเงินบน node มากที่สุด (เดิน node ซ้ำไม่ได้เงินเพิ่ม)

จากข้อนี้ หลายคนตอนเห็นโจทย์ ถ้าไม่รู้จัก SCC มาก่อนอาจจะเริ่มรู้สึกแบบ WTF? เพราะกราฟมีทั้ง cycle มีทั้งจบได้หลายที่ อ๊ากกกกกก
แต่ว่า ถ้าเกิดกราฟนี้เป็น DAG (พูดง่ายๆคือ เอา cycle ออกไป) ล่ะ? ง่ายขึ้นละเปล่า ถ้าทำได้ BFS รอบเดียวก็จบ หรือ DFS แบบ Dynamic รอบเดียวก็จบ ใครที่ไม่รู้ว่า dynamic ยังไง ลองอ่านที่ Dynamic Programming 2

ถ้าเกิดการทำให้กราฟนี้เป็น DAG แล้วแก้ง่ายขึ้น ก็ลองคิดว่า ทำ SCC ได้ละเปล่า (การรวม node จะทำให้แก้โจทย์ไม่ได้หรือไม่?)

ในข้อนี้ การรวม node ที่สามารถไปหากันได้ทุก node ในนั้น ให้กลายเป็น node เดียว (condensation) ก็ไม่ทำให้โจทย์เปลี่ยนแปลง เพราะค่าของเงินใน ATM ไม่มีติดลบ แปลว่า ถ้าต้องการเดินเก็บให้ได้มากที่สุด ก็ต้องเดินให้หมดในทุก node SCC ที่มี node ที่เราจะไปอยู่แน่นอน (เพราะอย่างไรก็ตาม ใน SCC สามารถไปหากันได้ทุก node จึงสามารถเดินเก็บเงินทั้งหมดได้)

ถึงตรงนี้ใครไม่เข้าใจ งงอะไร โพสต์ถามใน comment ได้เลยนะครับ

Algorithm ในการหา SCC

มีหลักๆอยู่ 3 algorithms แต่จริงๆไม่ต้องรู้หมด เอาให้เขียนได้ก็พอ algo ที่นิยมกันคือ Kosaraju’s Algorithm และ Tarjan’s SCC Algorithm ในที่นี้จะขอพูดถึง Kosaraju เพราะผมก็ยังไม่เคยใช้ Tarjan’s เลย

หลักการทำงาน

1. รัน DFS ใน graph แล้วจำ finish time ของแต่ละ node ไว้ (finish time คือเวลาที่ออกจากฟังชั่น DFS ของ node นั้นๆ เพื่อไม่ให้งง จะยกตัวอย่าง code ที่ใช้ DFS node และ หาค่า finish time ของแต่ละ node เพื่อให้เป็น idea
   

   int time = 0, top=0; << ตัวแปร global
   int finishtime[n], visited[n], stack[n];
    
   DFS(node V)
   {
          visited[V] = 1;
          for all node I adjacent node to V
             if( visited[I] != 1) DFS(I);
          finishtime[V] = time++;
          stack[top++] = V;
   }
    
   for all node I ( if (visited[I] != 1) DFS(I);

2. ทำการ transpose graph คือกลับทิศทาง edge ให้หมด ซึ่งสามารถทำได้ตั้งแต่การรับข้อมูลกราฟ โดยสร้างกราฟไว้อีกอันที่มีทิศทาง edge สลับกับกราฟจริง

3. ทำ DFS อีกครั้งบน transposed graph แต่ ลำดับ node ที่จะเข้าไปทำ DFS นั้น ให้เริ่มทำตาม finish time จากมากไปน้อย หรือก็คือ ค่อยๆ pop stack ออกมานั่นเอง (เพราะตัวที่เข้าไปท้ายสุดจะมี finish time มากสุด) สมมติให้การ DFS บน transposed graph ใช้ฟังชั่น DFSt
   สมมติให้ node ที่ pop ออกมาคือ I, ถ้าเกิด I ยังไม่เคยถูกไปมาก่อน ก็ให้ DFSt I ซะ ทุก node ที่สามารถ DFSt ไปถึงได้จาก I จะอยู่ใน SCC เดียวกับ I

int visited2[n], component[n], componentnumber=1;
 
DFSt(node V)
{
       visited2[V] = 1;
       component[V] = componentnumber;
       for all node I adjacent to node V in transposed graph
          if( visited2[I] != 1) DFSt(I);
}
 
while(stack not empty)
{
     now = stack.top();
     stack.pop();
     if( visited2[now] != 1) DFSt(now);
     componentnumber++;
}

เพียงเท่านี้ เราก็จะได้ SCC ของ graph มาแล้ว โดยค่า component[v] จะบอกว่า node v อยู่ใน component หมายเลขอะไร

ขั้นตอนต่อไปสำหรับการแก้ข้อนี้ คือการสร้าง condensed graph ซึ่งทำได้ไม่ยาก โดยเราจะถือว่า กราฟใหม่มี node เป็นแต่ละ component และถ้าหาก node ใดๆ ใน component A มี edge ไปหา node ใดๆ ใน component B ก็จะมี edge จาก A -> B เพียงเท่านี้ ก็จะได้ condensed graph มาใช้แก้ปัญหาข้อนี้แล้ว