【模板】拓扑排序

C 解法, 执行用时: 67ms, 内存消耗: 7800KB, 提交时间: 2022-08-06

#include<stdio.h>
#include<string.h>
#define N 200005
typedef struct listnode
{
int num; 
struct listnode *next;
}Node;
Node h[N],*p,*head,*a[N];
int main()
{
	int max=1,i,k=0,cnt=0,n,m,u,v,b[N],c[N],t=0;
    memset(c, 0, sizeof(c));
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&u,&v);
		c[v]++;
		p=&h[t++];
		p->num=v;
		p->next=NULL;
        head=a[u];
        if(head!=NULL) 
		{
		head->next=p;
		p=head;
		}
        else a[u]=p;
		if(u>max) max=u;
		if(v>max) max=v;
	}
	for(i=1;i<=max;i++)
	if(c[i]==0)
	b[k++]=i;
	while(cnt<k)
	{
		u=b[cnt];
		for(p=a[u];p!=NULL;p=p->next)
		{
			c[p->num]--;
			if(c[p->num]==0)
			b[k++]=p->num;
		}
		cnt++;
	}
	if(k<max) printf("-1");
    else
    {
	for(i=0;i<k-1;i++)
	printf("%d ",b[i]);
	printf("%d",b[k-1]);
    }
	return 0;
}

C++ 解法, 执行用时: 68ms, 内存消耗: 6380KB, 提交时间: 2022-05-25

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
vector<int> res;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],d[b]++,h[a] = idx++;
}
bool topSort(){
    int hh = 0,tt = -1;
    for(int i = 1;i<=n;i++){
        if(d[i] == 0){
            q[++tt] = i;
        }
    }
    while(hh <= tt){
        int t = q[hh++];
        res.push_back(t);
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(--d[j] == 0){
                q[++tt] = j;
            }
        }
    }
    return tt == n-1;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    bool ans = topSort();
    if(ans){
        for(int i = 0;i<res.size();i++){
            printf("%d",res[i]);
            if(i != res.size() - 1){
                printf(" ");
            }
        }
    }else{
        printf("-1");
    }
    
    
}

C++ 解法, 执行用时: 74ms, 内存消耗: 8516KB, 提交时间: 2022-07-07

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 200005;
const int INF = 0x7fffffff;
typedef long long LL;

struct edge {
	int to;
	int next;
}Edge[maxn];
int head[maxn];
int cntx = 0;
void add(int u, int v) {
	Edge[cntx].to = v;
	Edge[cntx].next = head[u];
	head[u] = cntx++;
}
int d[maxn];
int ans[maxn];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	fill(head, head + maxn, -1);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		d[v]++;
	}
	queue<int> my;
	int num = 0;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0)my.push(i);
	}
	while (!my.empty()) {
		int x = my.front();
		my.pop();
		ans[++num] = x;
		for (int i = head[x]; i != -1; i = Edge[i].next) {
			int y = Edge[i].to;
			d[y]--;
			if (d[y] == 0)my.push(y);
		}
	}
	if (num != n)cout << -1;
	else {
		cout << ans[1];
		for (int i = 2; i <= n; i++)cout << " " << ans[i];
		//cout << endl;
	}

	return 0;
}

C 解法, 执行用时: 75ms, 内存消耗: 7800KB, 提交时间: 2022-06-15

//对一个有向无环图G进行拓扑排序，
//是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
#include <stdio.h>
#include <string.h>
typedef struct _TN{
	int v;
	struct _TN *r;
}TN;
int stack[200010],in[200010];
TN heap[200010],*p,*hd;
int hpn=0;
TN *A[200010];
int main()
{
	int N,M,u,v,i,start,cnt;
	//memset(A, 0, sizeof(A));
	//memset(in, 0, sizeof(in));
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) {A[i]=NULL;in[i]=0;}
	for(int m=1;m<=M;m++) {
		scanf("%d%d",&u,&v);
		in[v]++;
		p=&heap[hpn++]; p->v=v;p->r=NULL;
		hd=A[u]; 
		if(hd) {p->r=hd->r;hd->r=p;}
		else A[u]=p;
	}
	cnt=0;
	for(i=1;i<=N;i++) {
		if(0 == in[i]) {
			stack[cnt++]=i;
		}
	}
	start=0;
	while(start<cnt) {
		u=stack[start];
		for(p=A[u];p;p=p->r) {
			v=p->v; in[v]--;//删除u关联的边
			if(0 == in[v]) {
				stack[cnt++]=v;
			}
		}
		start++;
	}
	if(cnt<N) {
        printf("-1\n");
        return 0;
    }
	for(i=0;i<cnt-1;i++) printf("%d ",stack[i]);
	printf("%d\n",stack[i]);
	return 0;
}

C 解法, 执行用时: 87ms, 内存消耗: 12312KB, 提交时间: 2022-06-26

#include<stdio.h>
#include<stdlib.h>

typedef struct EdgeNode{
    int adjext;
    struct EdgeNode* next;
}EdgeNode;

typedef struct VerteNode{
    int in;
    int data;
    struct VerteNode* firstEdge;
}VerteNode;

typedef struct{
    VerteNode adjList[200000];
    int numsNode,numsEdge;
}GraphAdjList;

int nums=0;

void CreateALGraph(GraphAdjList* G){
    int i,j,k;
    for(i=0;i<G->numsNode;i++){
        G->adjList[i].data=i;
        G->adjList[i].firstEdge=NULL;
        G->adjList[i].in=0;
    }
    for(k=0;k<G->numsEdge;k++){
        EdgeNode* e;
        scanf("%d",&i);
        scanf("%d",&j);
        e=(EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjext=j-1;
        e->next=G->adjList[i-1].firstEdge;
        G->adjList[i-1].firstEdge=e;
        G->adjList[j-1].in++;
    }
}

int TopologicalSort(GraphAdjList* G,int* ans){
    int i,j,gettop;
    int top=0;
    EdgeNode* e;
    int count=0;
    int* Queue=(int*)malloc(sizeof(int)*G->numsNode);
    int front=0,rear=0;
    for(int i=0;i<G->numsNode;i++){
        if(G->adjList[i].in==0)
            Queue[rear++]=i;
    }
    while(front!=rear){
        gettop=Queue[front++];
        ans[nums++]=G->adjList[gettop].data+1;
        count++;
        for(e=G->adjList[gettop].firstEdge;e;e=e->next){
            j=e->adjext;
            if(!(--G->adjList[j].in))
               Queue[rear++]=j;
        }
    }
    if(count==G->numsNode)
        return 1;
    else
        return -1;
}

int main(){
    GraphAdjList* G=(GraphAdjList*)malloc(sizeof(GraphAdjList));
    scanf("%d",&G->numsNode);
    scanf("%d",&G->numsEdge);
    int* ans=(int*)malloc(sizeof(int)*G->numsNode);
    CreateALGraph(G);
    int flag=TopologicalSort(G,ans);
    if(flag==-1)
        printf("-1");
    else{
        for(int i=0;i<nums;i++){
            if(i==0)
                printf("%d",ans[i]);
            else
                printf(" %d",ans[i]);
        }
    }
    return 0;
}

详情