lw

用户名：saudade

访问量：13800

签　名：

等　　级
排　　名	175
经　　验	6859
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

得得得得得
浏览：249

你可能喜欢

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

蓝桥杯算法提高VIP-士兵排队问题-题解（C++代码）拓扑+去重

　　作者: lw　　　　发表时间：2020-09-10 11:14:23 浏览：854　|　评论：1　

原题链接：蓝桥杯算法提高VIP-士兵排队问题

### 很迷的一道题，就是简单的拓扑排序加去重，求大佬指点
####AC：
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> G[300];
vector<int> ans;
set<int> peo;
int in[300], cnt;
bool vis[300];
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0); 
	string res;
	while (getline(cin, res)) {
		int p1 = res[0] - 'A';
		int p2 = res[2] - 'A';
		peo.insert(p1);
		peo.insert(p2);
		G[p1].push_back(p2);
		in[p2] ++;
	}
	cnt = peo.size();
	queue<int> q;
	for (set<int>::iterator it = peo.begin(); it != peo.end(); ++ it) {
		int p = *it;
		if(!in[p]) {
			q.push(p);
			vis[p] = true;
		}
	}
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		cnt --;
		ans.push_back(p);
		if(!cnt) {
			int l = ans.size();
			for(int i = 0; i < l; ++ i) {
				cout << (char) ('A' + ans[i]);
			}	
		}
		int l = G[p].size();
		for(int i = 0; i < l; ++ i) {
			int u = G[p][i];
			in[u] --;
		}
		for (set<int>::iterator it = peo.begin(); it != peo.end(); ++ it) {
			int u = *it;
			if (!in[u] && !vis[u]) {
				vis[u] = true;
				q.push(u);
			}
		}
	}
	if(cnt) cout << "No Answer!" ;
	return 0;
}
```
#### 82分：
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> G[300];
vector<int> ans;
set<int> peo;
int in[300];
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0); 
	string res;
	while (getline(cin, res)) {
		int p1 = res[0] - 'A';
		int p2 = res[2] - 'A';
		peo.insert(p1);
		peo.insert(p2);
		G[p1].push_back(p2);
		in[p2] ++;
	}
	queue<int> q;
	for (set<int>::iterator it = peo.begin(); it != peo.end(); ++ it) {
		int p = *it;
		if(!in[p]) {
			q.push(p);
			peo.erase(p);
		}
	}
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		ans.push_back(p);
		if(peo.empty() && q.empty()) {
			int l = ans.size();
			for(int i = 0; i < l; ++ i) {
				cout << (char) ('A' + ans[i]);
			}	
		}
		int l = G[p].size();
		for(int i = 0; i < l; ++ i) {
			int u = G[p][i];
			in[u] --;
		}
		for (set<int>::iterator it = peo.begin(); it != peo.end(); ++ it) {
			int u = *it;
			if (!in[u]) {
				q.push(u);
				peo.erase(u);
			}
		}
	}
	if(!peo.empty()) cout << "No Answer!" ;
	return 0;
}
```
#### 73分：
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> G[300];
vector<int> ans;
set<int> peo;
int in[300], cnt;
bool vis[300];
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0); 
	string res;
	while (getline(cin, res)) {
		int p1 = res[0] - 'A';
		int p2 = res[2] - 'A';
		peo.insert(p1);
		peo.insert(p2);
		G[p1].push_back(p2);
		in[p2] ++;
	}
	cnt = peo.size();
	queue<int> q;
	for (set<int>::iterator it = peo.begin(); it != peo.end(); ++ it) {
		int p = *it;
		if(!in[p]) {
			q.push(p);
			vis[p] = true;
		}
	}
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		cnt --;
		ans.push_back(p);
		if(!cnt) {
			int l = ans.size();
			for(int i = 0; i < l; ++ i) {
				cout << (char) ('A' + ans[i]);
			}	
		}
		int l = G[p].size();
		for(int i = 0; i < l; ++ i) {
			int u = G[p][i];
			in[u] --;
			if (!in[u] && !vis[u]) {
				vis[u] = true;
				q.push(u);
			}
		}
	}
	if(cnt) cout << "No Answer!" ;
	return 0;
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

早起床

为什么要去重复啊，拓扑排序应该是没有重复的元素会被再次push进去的吧

2022-10-13 12:31:07

lw

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-士兵排队问题-题解（C++代码）拓扑+去重

评论区

精彩推荐

矩阵转置（C语言代码）

剔除相关数（C语言代码）

兰顿蚂蚁（C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

最小公倍数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

罗列完美数（C语言代码）

lw

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-士兵排队问题-题解（C++代码）拓扑+去重

评论区

精彩推荐

矩阵转置 （C语言代码）

剔除相关数 （C语言代码）

兰顿蚂蚁 （C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

最小公倍数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

罗列完美数 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

　　评论区

矩阵转置（C语言代码）

剔除相关数（C语言代码）

兰顿蚂蚁（C++代码）

C语言考试练习题_一元二次方程（C语言代码）

最小公倍数（C语言代码）

罗列完美数（C语言代码）