1 条题解

  • 0
    @ 2025-4-7 21:19:28

    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
    1091
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者