Uva 10305 - Ordering Tasks 拓撲排序基礎水題 隊列和dfs實現

今天剛學的拓撲排序，大概搞懂後發現這題是赤裸裸的水題。

於是按自己想法敲了一遍，用queue做的，也就是Kahn算法，復雜度o(V+E)，調完交上去，WA了。。。

於是檢查了一遍又交了一發，還是WA。。。

我還以為是用queue的問題，改成stack也WA，然後干脆放棄STL，手敲了隊列，還是WA了。。。

我抓狂了。

感覺沒什麼問題的，卡了我一個多小時。最後用樣例0 1測試，發現是在輸入的循環判斷時出錯了，他要求兩個都為0時結束，我只要有一個為0就結束了。。。

坑爹，血的教訓。。。

然後我把之前的代碼修改後都過了，還嘗試了dfs。

於是：

用queue過的：

#include <cstdio>  
#include <cstring>  
#include <queue>  
using namespace std; 
const int maxn = 101; 
int n, m; 
int indegree[maxn] = {0}, gragh[maxn][maxn], res[maxn]; 
 
void topologic(void) { 
    queue <int> q; 
    int cnt = 0; 
    for (int i = 0; i < n; i++)  
        if (indegree[i] == 0) 
            q.push(i); 
    while (!q.empty()) { 
        int tmp = q.front(); 
        q.pop(); 
        res[cnt++] = tmp; 
        for (int i = 0; i < n; i++) 
            if (gragh[tmp][i] != 0) 
                if (--indegree[i] == 0) 
                    q.push(i); 
    }//while  
    printf("%d", res[0] + 1); 
    for (int i = 1; i < cnt; i++) 
        printf(" %d", res[i] + 1); 
    printf("\n"); 
} 
 
 
int main() { 
    while (scanf("%d%d", &n, &m) && (n || m)) { 
        memset(gragh, 0, sizeof(gragh)); 
        memset(indegree, 0, sizeof(indegree)); 
        int a, b; 
        for (int i = 0; i < m; i++) { 
            scanf("%d%d", &a, &b); 
            gragh[a-1][b-1] = 1; 
            indegree[b-1]++; 
        }//for input  
        /*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) 
            printf("%d ", gragh[i][j]);
        printf("\n");
    }
    for (int i = 0; i < n; i++) 
        printf("%d ", indegree[i]);
    printf("\n");
*/ 
        topologic(); 
    }//while  
    return 0; 
} 

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 101;
int n, m;
int indegree[maxn] = {0}, gragh[maxn][maxn], res[maxn];

void topologic(void) {
 queue <int> q;
 int cnt = 0;
 for (int i = 0; i < n; i++)
  if (indegree[i] == 0)
   q.push(i);
 while (!q.empty()) {
  int tmp = q.front();
  q.pop();
  res[cnt++] = tmp;
  for (int i = 0; i < n; i++)
   if (gragh[tmp][i] != 0)
    if (--indegree[i] == 0)
     q.push(i);
 }//while
 printf("%d", res[0] + 1);
 for (int i = 1; i < cnt; i++)
  printf(" %d", res[i] + 1);
 printf("\n");
}


int main() {
 while (scanf("%d%d", &n, &m) && (n || m)) {
  memset(gragh, 0, sizeof(gragh));
  memset(indegree, 0, sizeof(indegree));
  int a, b;
  for (int i = 0; i < m; i++) {
   scanf("%d%d", &a, &b);
   gragh[a-1][b-1] = 1;
   indegree[b-1]++;
  }//for input
  /*
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++)
   printf("%d ", gragh[i][j]);
  printf("\n");
 }
 for (int i = 0; i < n; i++)
  printf("%d ", indegree[i]);
 printf("\n");
*/
  topologic();
 }//while
 return 0;
}

手敲隊列：

#include <cstdio>  
#include <cstring>  
const int maxn = 101; 
 
int g[maxn][maxn], id[maxn], q[maxn]; 
 
int main() { 
//  freopen("in", "r", stdin);  
    int n, m, a, b, tmp; 
    int front, tail; 
    while (scanf("%d%d", &n, &m)) { 
        if (n == 0 && m == 0) 
            break; 
        memset(g, 0, sizeof(g)); 
        memset(id, 0, sizeof(id)); 
        front = tail = 0; 
        for (int i = 0; i < m; i++)  { 
            scanf("%d%d", &a, &b); 
            g[a][b] = 1; 
            id[b]++; 
        } 
        for (int i = 1; i <= n; i++) 
            if (id[i] == 0) 
                q[tail++] = i; 
        while (tail != front) { 
            tmp = q[front++]; 
            if (front == 1) 
                printf("%d", tmp); 
            else 
                printf(" %d", tmp); 
            for (int i = 1; i <= n; i++) 
                if (g[tmp][i] != 0) 
                    if (--id[i] == 0) 
                        q[tail++] = i; 
        }//while  
        printf("\n"); 
    }//while   
    return 0; 
} 

#include <cstdio>
#include <cstring>
const int maxn = 101;

int g[maxn][maxn], id[maxn], q[maxn];

int main() {
// freopen("in", "r", stdin);
 int n, m, a, b, tmp;
 int front, tail;
 while (scanf("%d%d", &n, &m)) {
  if (n == 0 && m == 0)
   break;
  memset(g, 0, sizeof(g));
  memset(id, 0, sizeof(id));
  front = tail = 0;
  for (int i = 0; i < m; i++)  {
   scanf("%d%d", &a, &b);
   g[a][b] = 1;
   id[b]++;
  }
  for (int i = 1; i <= n; i++)
   if (id[i] == 0)
    q[tail++] = i;
  while (tail != front) {
   tmp = q[front++];
   if (front == 1)
    printf("%d", tmp);
   else
    printf(" %d", tmp);
   for (int i = 1; i <= n; i++)
    if (g[tmp][i] != 0)
     if (--id[i] == 0)
      q[tail++] = i;
  }//while
  printf("\n");
 }//while
 return 0;
}

dfs方法：

#include <cstdio>  
#include <cstring>  
#include <queue>  
using namespace std; 
const int maxn = 101; 
int n, m, t; 
int gragh[maxn][maxn], res[maxn], c[maxn]; 
 
bool dfs(int u) { 
    c[u] = -1; 
    for (int v = 0; v < n; v++) 
        if (gragh[u][v]) 
            if (c[v] < 0) 
                return false; 
            else if (!c[v] && !dfs(v)) 
                return false; 
    c[u] = 1; 
    res[--t] = u; 
    return true; 
} 
 
bool toposort() { 
    t = n; 
    memset(c, 0, sizeof(c)); 
    for (int u = 0; u < n; u++) 
        if (!c[u]) 
            if (!dfs(u)) 
                return false; 
    return true; 
} 
 
int main() { 
    while (scanf("%d%d", &n, &m) && (n || m)) { 
        memset(gragh, 0, sizeof(gragh)); 
        int a, b; 
        for (int i = 0; i < m; i++) { 
            scanf("%d%d", &a, &b); 
            gragh[a-1][b-1] = 1; 
        }//for input  
        toposort(); 
        for (int i = 0; i < n; i++) 
            printf("%d ", res[i] + 1); 
        printf("\n"); 
    }//while  
    return 0; 
} 

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 101;
int n, m, t;
int gragh[maxn][maxn], res[maxn], c[maxn];

bool dfs(int u) {
 c[u] = -1;
 for (int v = 0; v < n; v++)
  if (gragh[u][v])
   if (c[v] < 0)
    return false;
   else if (!c[v] && !dfs(v))
    return false;
 c[u] = 1;
 res[--t] = u;
 return true;
}

bool toposort() {
 t = n;
 memset(c, 0, sizeof(c));
 for (int u = 0; u < n; u++)
  if (!c[u])
   if (!dfs(u))
    return false;
 return true;
}

int main() {
 while (scanf("%d%d", &n, &m) && (n || m)) {
  memset(gragh, 0, sizeof(gragh));
  int a, b;
  for (int i = 0; i < m; i++) {
   scanf("%d%d", &a, &b);
   gragh[a-1][b-1] = 1;
  }//for input
  toposort();
  for (int i = 0; i < n; i++)
   printf("%d ", res[i] + 1);
  printf("\n");
 }//while
 return 0;
}

 

這次是血淋淋的教訓啊：

一、輸入部分一定要提前測試

二、測試數據要多一點，多想些特殊測試點

三、必須提高敲題效率。