A17482. 专属教室
填空题
困难
知识点
题目描述
专属教室
题目描述
在一所学校中，有 N 个班级，每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si，但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同，所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室，且一次只能安排一个班级进行更换。在更换时，目标教室必须是空闲的。
学校希望找到一个合理的更换顺序，使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行，每行两个字符串 Si 和 Ti，表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换，输出 Yes，否则输出 No。
输入样例#1
2
b m
m d输出样例#1
Yes输入样例#2
3
a b
b c
c a输出样例#2
No说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串，长度在 1 到 8 之间。
Si≠Ti
所有 Si互不相同。
所有 Ti互不相同。
参考答案
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<string, vector<string>> adj;
map<string, int> state;
bool has_cycle(string v) {
state[v] = 1;
for (string next_v : adj[v]) {
if (state[next_v] == 1) return true;
if (state[next_v] == 0) {
if (has_cycle(next_v)) return true;
}
}
state[v] = 2;
return false;
}
int main() {
int N;
cin >> N;
vector<string> S(N), T(N);
for (int i = 0; i < N; i++) {
cin >> S[i] >> T[i];
adj[S[i]].push_back(T[i]);
}
for (auto const& [name, _] : adj) {
if (state[name] == 0) {
if (has_cycle(name)) {
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}
上一题
下一题