PAT 1034 Head of a Gang——建图中最快算法（DFS和map+vector）

感谢：iaccepted 提供的基本思路，即用map+vector建图

 

分析

此题考察： 找 各个连通图 

此题 最大坑：非数字点

其他小坑：字母序输出，帮派成员数量、点权（找头目）和边权（判断阈值）

 

代码层面解析

找 各个连通图 ——》DFS

非数字坑——》map+vector

字母序输出——》set存储

帮派成员数量——》map映射set成员

点权和边权——》分别用2个int 记录

 

代码

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

int quantity, threthold, number{ 0 }, summary, head_key, gang_number;
string head;
set<string> gang;
unordered_map<string, int>key, gang_n;
unordered_map<string, vector<string> >graph;
unordered_map<string, bool>mark;

void InPut();
void DFS(string);
int main() {
	InPut();
	while (number < mark.size()) {
		for (auto j = mark.begin(); j != mark.end(); j++) {
			summary = 0;
			gang_number = 0;
			if (mark[j->first] == false) {
				head_key = key[j->first];
				head = j->first;
				DFS(j->first);
			}
			if (summary / 2 > threthold && gang_number > 2) {
				gang.insert(head);
				gang_n[head] = gang_number;
			}
		}
	}
	printf("%d\n", gang.size());
	if (gang.size() > 0) {
		for (auto i = gang.begin(); i != gang.end(); i++) {
			cout << *i << " " << gang_n[*i] << "\n";
		}
	}
	return 0;
}
void InPut() {
	scanf("%d %d", &quantity, &threthold);
	string x, y;
	int z;
	for (int i = 0; i < quantity; i++) {
		cin >> x >> y >> z;
		graph[x].push_back(y);
		graph[y].push_back(x);
		key[x] += z;
		key[y] += z;
		mark[x] = false;
		mark[y] = false;
	}
}
void DFS(string id) {
	number++;
	mark[id] = true;

	summary += key[id];
	gang_number++;
	if (key[id] > head_key) {
		head_key = key[id];
		head = id;
	}
	for (auto k : graph[id]) {
		if (mark[k] == false)
			DFS(k);
	}
}

后记

在map实现上用到了unordered_map可以在最大边界 稳定缩短2、3秒

原因是map底层是红黑树，unordered_map是散列

unordered_map

map