拓扑排序

喜欢ヅ旅行 2021-06-22 15:37 519阅读 0赞

## 作用：判断是否存在环 ##

1.数组模拟队列

#include <iostream>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn=1e5+10;

int h[maxn],e[maxn],ne[maxn],idx,d[maxn];//d[]表示该点的入度 
    int q[maxn],hh,tt=-1;
    int n,m;

void add(int a,int b){ //邻接表
    	e[idx]=b;
    	ne[idx]=h[a];
    	h[a]=idx++;
    }

bool top_sort(){ 
    	for(int i=1;i<=n;i++){ 
    		 if(d[i]==0){ 
    		 	q[++tt]=i;// 将所有入度为0的点加入队列
    		 }
    	}
    	while(tt>=hh){ 
    		int t=q[hh++];//取出队头删掉队头 
    		for(int i=h[t];i!=-1;i=ne[i]){ 
    			   int j=e[i];
    			   d[j]--;
    			   if(d[j]==0){ 
    			   	 q[++tt]=j;//如果 j 入度为0，加入队列当中
    			   }
    		}
    	}
    	if(tt==n-1){ //如果队列已经存放满了n个元素说明没有环 
    		return true;
    	}
        return false;
    }

int main(){ 
    	memset(h,-1,sizeof(h));//初始化链表的表头 
    	cin>>n>>m;
    	while(m--){ 
    		int a,b;
    		cin>>a>>b;
    		add(a,b);
    		d[b]++;//b的入度加1 
    	}
    	if(top_sort()){ 
    		for(int i=0;i<=tt;i++){ //如果是真说明不存在环直接把队列的元素输出
    		 cout<<q[i]<<" ";
    	}
    	}
    	else{ 
    		cout<<-1<<endl;//有环不存在拓扑序列
    	}
    	return 0;
    }

2.stl容器

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <queue>
    using namespace std;
    const int maxn=1e5+10;

int n,m;
    vector<int> ans;
    int h[maxn],e[maxn],ne[maxn],idx,d[maxn];//d[]表示该点的入度

void add(int a,int b){ 
    	e[idx]=b;
    	ne[idx]=h[a];
    	h[a]=idx++;
    }

bool top_sort(){ 
    	queue<int> q;
    	for(int i=1;i<=n;i++){ 
    		 if(d[i]==0){ 
    		 	q.push(i);// 将所有入度为0的点加入队列
    		 }
    	}
    		 while(!q.empty()){ //当队列不空时 
    		 	 int t=q.front();
    		 	ans.push_back(t);//存起来备份方便输出 
    		 	 q.pop();
    		 	 for(int i=h[t];i!=-1;i=ne[i]){ 
    		 	 	    int j=e[i];
    		 	 	    d[j]--;//减去已经前一个点到当前该点的入度 
    		 	 	    if(d[j]==0){ 
    		 	 	    	q.push(j);//如果 j 入度为0，加入队列当中
    					  }
    			  }	 
    		 }
    	
    	if(ans.size()==n){ 
    		return true;//如果队列已经存放满了n个元素说明没有环 
    	}
    	return false;
    }

int main(){ 
    	memset(h,-1,sizeof(h));//初始化链表的表头 
    	cin>>n>>m;
    	while(m--){ 
    		int a,b;
    		cin>>a>>b;
    		add(a,b);
    		d[b]++;//b的入度加1 
    	}
    	if(top_sort()){ 
    		for(int i=0;i<ans.size();i++){ 
    		 cout<<ans[i]<<" ";
    	}
    	}
    	else{ 
    		cout<<-1<<endl;
    	}
    	
    }