D - Change Usernames

传送门

  username  Si 可以 变成 Ti， 但是同时只能有一个独一无二的 Si  进行变化， 画个图会发现就是看这个图中是否有环存在， 做法如下

三种方法求简单图中是否有环

a) 并查集

Initially create subsets containing only a single node which are the parent of itself. Now while traversing through the edges, if the two end nodes of the edge belongs to the same set then they form a cycle. Otherwise, perform union to merge the subsets together.

Note: This method assumes that the graph doesn’t contain any self-loops.

合并两条边的时候， 如果他们属于同一集合 那么存在环

b) 拓扑排序

 若图中存在环， 则不能拓扑排序

c) DFS

  如果在遍历 a 节点的子节点 又跳到 a 节点时， 说明有环
（ps ：这题有个问题就是明明是 有向边 但是要当成无向边 存储， 没懂

  1 
  2 
  3 #include <bits/stdc++.h>
  4 
  5 using namespace std;
  6 
  7 typedef long long ll;
  8 
  9 const int N = 2e5 + 10;
 10 
 11 int n, m;
 12 
 13 vector<int> G[N];
 14 int used[N], fa[N];
 15 int findfa(int x) {
 16     return x == fa[x] ? x: fa[x] = findfa(fa[x]);
 17 }
 18 
 19 // vector<int> edge[N + 1];
 20 int q[N + 1], d[N + 1];// queue degree
 21 
 22 inline void TopoSort() {
 23     int front = 1, rear = 0;
 24     for (int i = 1; i <= n; i++)
 25         if (!d[i])
 26             q[++rear] = i;
 27     while (front <= rear) {
 28         int x = q[front++];
 29         for (int y : G[x]) {
 30             if (--d[y] == 0)
 31                 q[++rear] = y;
 32         }
 33     }
 34 
 35     if (rear == n)
 36         printf("Yes\n");
 37     else 
 38         printf("No\n");
 39 }
 40 bool dfs(int x, int fa) {
 41     used[x] = 1;
 42     for (auto y : G[x]) {
 43         if (y != fa) {
 44             if (used[y])
 45                 return true;
 46             if (dfs(y, x))
 47                 return true;
 48         }
 49     }
 50     return false;
 51 }
 52 void solve() {
 53     scanf("%d", &m);
 54     map<string, int> mp;
 55     int cnt = 0, ok = 0;
 56     for (int i = 0; i < N; i++)
 57         fa[i] = i;
 58     for (int i = 0; i < m; i++) {
 59         char s1[10], s2[10];
 60         // scanf("%s%s", s1, s2);
 61         string str1 = s1, str2 = s2;
 62         cin >> str1 >> str2;
 63         if (!mp.count(str1))
 64             mp[str1] = ++cnt;
 65         if (!mp.count(str2))
 66             mp[str2] = ++cnt;
 67         G[mp[str1]].push_back(mp[str2]);
 68         G[mp[str2]].push_back(mp[str1]);
 69 
 70         // printf("%d -> %d\n", mp[str1], mp[str2]);
 71         
 72         // G[mp[str1]].push_back(mp[str2]);
 73         // d[mp[str2]]++;
 74         // toposort
 75 
 76         /*  并查集
 77         int fx = findfa(mp[str1]);
 78         int fy = findfa(mp[str2]);
 79         if (fx != fy) fa[fx] = fy;
 80         else {
 81             ok = 1;
 82         }
 83         */
 84     }
 85     
 86     // dfs
 87     for (int i = 1; i <= cnt; i++) {
 88         if (!used[i])
 89             ok |= dfs(i, -1);
 90         if (ok) break;
 91     }
 92     printf(ok ? "No\n" : "Yes\n");
 93 
 94     // 拓扑排序
 95     // n = cnt;
 96     // TopoSort();
 97 }
 98 
 99 int main() {
100     int test = 1;
101     // scanf("%d", &test);
102     while (test--) 
103         solve();
104     return 0;
105 }