subject

Title Link

Problem solution

Topological sorting (there should be other methods, but for this kind of problem, topology is the general solution).
This solution is friendly to students who can understand topology and STL. Students who can't can go to other blogs to learn. After all, it will always be used.

In the Blue Bridge Cup, I have also done several topology problems.
If you know topology, the problem is how to save and process data using appropriate STL.

After introducing the meaning of variables in the code in detail, it is best to cooperate with the code comments.
It is a topology template problem, but the data structure is troublesome and difficult to understand.

Map < string, int > ID: id[str] = c means that the number of string str is c. in this question, a name corresponds to a number. This data structure is used to record the number of each name. The reason why the numbering idea is adopted is that it will be more convenient to construct the undirected graph of topology later, but it is difficult to realize it with string;
ids: every time you encounter a string that does not appear, you should set the number ids for the string and a new string ids + + appears. Used to number strings;
string s1, s2: input string;
string ans[N]: the output topology sequence is output through this function, that is, save the answer. What is the string sorted as I by ans[i];
string nameofid[N]: the name corresponding to the number. nameofid[i] indicates the name with the number I;
Vector < string > Name: all names are saved here, and no duplicate is saved;
int ne[M], e[M], h[N], idx: these variables should be familiar, that is, several variables of the adjacency table. Both ne[i] and e[i] indicate that the number of the edge is the point number corresponding to I, and h[i] indicates that the name corresponds to the number of the edge corresponding to I;
T. N: such as the title;
in[N]: in[i] indicates the penetration corresponding to the name number I, which is used in topology sorting;
CNT: controls the number of ANS arrays. This topic means that there must be a topological sequence, so the number of elements of the final ans is actually the number of strings, that is, ids = cnt.

code

// https://www.dotcpp.com/oj/problem1506.html
#include<bits/stdc++.h>
using namespace std;
const int N = 110; // The title says that there are at most 13 people. I don't know why there can be no "operation error" only when it is driven to 100 + 
const int M = 110;


map<string, int> id;
int ne[M], e[M], h[N], T, n, in[N], cnt, ids, idx;
string s1, s2, ans[N], nameofid[N];
vector<string> name;

void add(int a, int b) { // The passed in parameter is the number corresponding to the name 
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void topsort() {
	
	int m = name.size();
	queue<string> q; // Element name 
	
	for(int i = 0;i < m;i ++) if(in[id[name[i]]] == 0) q.push(name[i]), ans[++cnt] = name[i]; // Add the name with the initial score of 0 to the queue and answer array 
	
	while(!q.empty()) {
		string t = q.front();
		q.pop();
		for(int i = h[id[t]];i != -1;i = ne[i]) { // id[t] is the id corresponding to the extracted team leader name, and h[id] represents the edge corresponding to the point id 
			int j = e[i]; // This is the number of the name 
			string ss = nameofid[j]; // Name corresponding to number 
			in[j]--; // Penetration-- 
			if(in[j] == 0) q.push(ss), ans[++cnt] = ss; // Join the queue and answer with a penetration of 0 
		}
	}
}

int main()
{
	cin>>T;
	while(T--) {
		cin>>n;
		
		// initialization 
		id.clear();name.clear();
		memset(in, 0, sizeof in);
		memset(h, -1, sizeof h);
		cnt = 0, idx = 0, ids = 0;
		
		while(n--) {
			cin>>s1>>s2;
			if(!id[s1]) id[s1] = ++ ids, nameofid[ids] = s1, name.push_back(s1); // New ids++ 
			if(!id[s2]) id[s2] = ++ ids, nameofid[ids] = s2, name.push_back(s2);
			add(id[s1], id[s2]);
			in[id[s2]] ++;
		}	
		
		topsort();
		
		for(int i = 1;i <= cnt;i ++) cout << ans[i] << ' '; cout<<endl;
	} 

	return 0;
}