1 条题解
-
0
C :
#include<stdio.h> #define MAX_VERTEX_NUM 60 #define TRUE 1 #define FALSE 0 typedef int AdjType; typedef int Type; typedef struct { int num; AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; }MGraph; void Push(int S[],int *n,int e) { S[(*n)++]=e; } Type Pop(int S[],int *n) { int e=S[--(*n)]; return e; } Type Empty(int S[],int *n) { if(!*n) return TRUE; else return FALSE; } void TopologicalSort(MGraph *G) { char indegree[MAX_VERTEX_NUM]={0}; int order[MAX_VERTEX_NUM]={0}; int k=0,count=0,n=0; int S[G->num]; for(int i=0;i<G->num;i++) { S[i]=-1; } for(int j=0;j<G->num;j++) { for(int i=0;i<G->num;i++) indegree[j]=indegree[j]+G->A[i][j]; if(!(indegree[j])) Push(S,&n,j); } while(!(Empty(S,&n))) { int top=Pop(S,&n); order[k++]=top; count++; for(int i=0;i<G->num;i++) { if((indegree[i]==1)&&(G->A[top][i]==1)) Push(S,&n,i); indegree[i]=indegree[i]-G->A[top][i]; } } if(count<G->num) { printf("ERROR\n"); } else { for(int i=0;i<k;i++) printf("%d ",order[i]); printf("\n"); } } int main() { MGraph G; int N; scanf("%d",&N); G.num=N; AdjType a[N][N]; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { scanf("%d",&a[i][j]); } } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { G.A[i][j]=a[i][j]; } } TopologicalSort(&G); return 0; }
C++ :
#include <cstdio> #include <cstdlib> #include <stack> #include <algorithm> using namespace std; const int MAXN = 50; int mat[MAXN][MAXN], output[MAXN], indegree[MAXN]; int n, outputCnt, current; stack<int> st; bool TopologicalSort() { outputCnt = 0; while (!st.empty()) st.pop(); for (int i = 0;i < n;i++) indegree[i] = 0; for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { if (mat[i][j]) indegree[j]++; } } for (int i = 0;i < n;i++) { if (indegree[i] == 0) { st.push(i); } } while (!st.empty()) { current = st.top(); st.pop(); output[outputCnt++] = current; for (int i = 0;i < n;i++) { if (mat[current][i]) { indegree[i]--; if (indegree[i] == 0) { st.push(i); } } } } return (outputCnt == n); } int main() { scanf("%d", &n); for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { scanf("%d", &mat[i][j]); } } if (TopologicalSort()) { for (int i = 0;i < n;i++) { printf("%d ", output[i]); } puts(""); } else { puts("ERROR"); } return 0; }
- 1
信息
- ID
- 521
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者