ACM: 125 – Numbering Paths

這題頗有挑戰性，給有向圖(directed graph)，要找出圖上是否有環(cycle)，也要找出所有點之間存在的所有路徑數量，當路徑經過環(即代表路徑數量無窮大)，路徑數量要輸出-1。

我的作法是先以dp(Floyd-Warshall做變化)找出所有點之間存在的所有路徑數量，接著判斷是否有k->k (k = 1….n)路徑存在，若存在即為環存在，再跑一次迴圈將所有可與k相連的路徑的值設為-1。

在寫的時候原本Floyd-Warshall的觀念還是沒想清楚，在最外面多加了一層算「經過幾個點」的迴圈，寫出來超冗長且bug連連。後來改用recursive去產出所有組合，想當然Time Limit Exceed。苦思良久才領悟到不必多加那一層迴圈，也搞清楚找到環以後如何去刪掉所有受影響的節點了。柳暗花明，最後看到了清爽的程式碼 :))

不過仍然是跑了兩次三層迴圈，應該算O(2 * n^3)吧，一定可以更省，就繼續研究吧。

CODE

#include <iostream>
using namespace std;

#define MAX 30

int main(){
  int i, j, k;
  int maxn, side, d1, d2, total;
  int matrix[MAX][MAX]; //total number of paths
  
  total = 0;
  while( cin >> side ){
    for(i=0; i<MAX; i++)
      for(j=0; j<MAX; j++)
        matrix[i][j] = 0;
        
    maxn = -1;
    for(i=0; i<side; i++){
      cin >> d1 >> d2;
      matrix[d1][d2] = 1;
      if( d1 > maxn ) maxn = d1;
      if( d2 > maxn ) maxn = d2;
    }
    maxn++;
  
    //findout all paths
    for(k=0; k<maxn; k++)
      for(i=0; i<maxn; i++)
        for(j=0; j<maxn; j++)
          if( matrix[i][k] * matrix[k][j] > 0 )
            matrix[i][j] += matrix[i][k];
    
    //eliminate paths involved cycles
    for(k=0; k<maxn; k++)
      if( matrix[k][k] != 0 ) //cycle
        for(i=0; i<maxn; i++)
          for(j=0; j<maxn; j++)
            if( matrix[i][k] * matrix[k][j] != 0 )
              matrix[i][j] = -1;
    
    //output
    cout << "matrix for city " << total << endl;
    for(i=0; i<maxn; i++){
      cout << matrix[i][0];
      for(j=1; j<maxn; j++)
        cout << ' ' << matrix[i][j];
      cout << endl;
    }
    
    total++;
  }//while
  return 0;
}