首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#12860

专属教室 题目描述 在一所学校中,有 N 个班级,每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 S i ,但学校计划将其调整到新的教室 T i…

专属教室

题目描述

在一所学校中,有 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 互不相同。

限制

时间限制:1000ms

内存限制:256MiB


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; #include &lt;map&gt; using namespace std; map&lt;string, vector&lt;string&gt;&gt; adj; map&lt;string, int&gt; 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 &gt;&gt; N;      vector&lt;string&gt; S(N), T(N);   for (int i = 0; i &lt; N; i++) {     cin &gt;&gt; S[i] &gt;&gt; T[i];     adj[S[i]].push_back(T[i]);   }      for (auto const&amp; [name, _] : adj) {     if (state[name] == 0) {       if (has_cycle(name)) {         cout &lt;&lt; "No" &lt;&lt; endl;         return 0;       }     }   }      cout &lt;&lt; "Yes" &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。