图论拓扑排序

解题思路:

注意事项:

参考代码:

#include <bits/stdc++.h> //就是一个字符串关系型的拓扑排序 
using namespace std;
struct node{
	int in;//入度 
	string info;//顶点信息 
};
map<string,vector<string> > mp;
map<string,int> inmp; //顶点信息 
queue<string> q;//队列
vector<vector<string> > ans;
vector<string> t;
int main(){
	int n,m;
	string str1,str2;
	cin>>n;
	while(n--){
		cin>>m; 
		for(int i=0;i<m;i++){
			cin>>str1>>str2;
			mp[str1].push_back(str2);
			inmp[str2]++;
			inmp[str1];
		}
		map<string,int>::iterator it=inmp.begin();
		while(it!=inmp.end()){
			if(it->second==0){
				q.push(it->first);
				break;
			}
			it++;
		}
		string str="";
		while(!q.empty()){
			string tm=q.front();
			t.push_back(tm);
			q.pop();
			for(int i=0;i<mp[tm].size();i++){
				str=mp[tm][i];
				inmp[str]--;
				if(inmp[str]==0) q.push(str);
			}
		}
		ans.push_back(t);
		t.clear();
		mp.clear();
		inmp.clear();
		queue<string> empty;
		swap(empty, q);	
	}
	for(int i=0;i<ans.size();i++){
		for(int j=0;j<ans[i].size();j++){
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}