首页 > 代码库 > Uva 10305 给任务排序

Uva 10305 给任务排序

题目链接:https://uva.onlinejudge.org/external/103/10305.pdf

紫书P167

拓扑排序。

dfs——从一个点出发,dfs 与之相连的所有点,把本身放入到拓扑排序的首部。

技术分享
#include <bits/stdc++.h>using namespace std;const int Maxn = 1000;int G[Maxn][Maxn];int topo[Maxn];int c[Maxn];int n,m,t;bool dfs(int u) {    c[u] = -1;    for(int v=0;v<n;v++) if(G[u][v]) {        if(c[v]<0) return false;        else if(!c[v]&&!dfs(v)) return false;    }    c[u] = 1;    topo[--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)==2&&n) {        memset(G,0,sizeof(G));        for(int i=0;i<m;i++) {            int u,v;            scanf("%d%d",&u,&v);            u--;            v--;            G[u][v] = 1;        }        if(toposort()) {            for(int i=0;i<n-1;i++) {                printf("%d ",topo[i]+1);            }            printf("%d\n",topo[n-1]+1);        }        else printf("No\n");    }    return 0;}
View Code

找入度为 0 的点,在这里开始删边。

技术分享
#include <bits/stdc++.h>using namespace std;const int Maxn = 1100;int G[Maxn][Maxn];int degree[Maxn];int ans[Maxn];int main(){    int n,m;    while(scanf("%d%d",&n,&m),n) {        memset(degree,0,sizeof(degree));        memset(G,0,sizeof(G));        for(int i=0;i<m;i++) {            int u,v;            scanf("%d%d",&u,&v);            u--;            v--;            G[u][v] = 1;            degree[v] ++;        }        int pos = 0;        for(int i=0;i<n;i++) {            for(int j=0;j<n;j++) {                if(degree[j]==0) {                    ans[pos++] = j;                    degree[j] = -1;                    for(int k=0;k<n;k++) {                        if(G[j][k]==1)                            degree[k]--;                    }                }            }        }        if(pos==n) {            for(int i=0;i<n-1;i++)                printf("%d ",ans[i]+1);            printf("%d\n",ans[n-1]+1);        }        else puts("No");    }    return 0;}
View Code

 

Uva 10305 给任务排序