【洛谷】 P1407 [國家集訓隊]穩定婚姻 （二分圖）

• #include <bits/stdc++.h>
  using namespace std;
  #define PII pair<int,int>
  #define fi first
  #define se second
  #define pb push_back
  #define ll long long
  #define ull unsigned long long
  const int N=1e6+10;
  
  int n,m;
  vector<int> edge[N];
  int id;
  map<string,int> tot;
  unordered_map<int,int> mp;
  bool boy[N];
  bool vis[N];
  
  bool dfs(int u){
      for(auto to:edge[u]){
          if(vis[to]) continue;
          vis[to]=true;
          if(mp[to]==0 || dfs(mp[to])) return true;
      }
      return false;
  }
  
  int main(){
      cin>>n;
      for(int i=1;i<=n;++i){
          string s,t;
          cin>>s>>t;
          if(!tot[s]) tot[s]=++id;
          if(!tot[t]) tot[t]=++id;
          mp[tot[s]]=tot[t];
          mp[tot[t]]=tot[s];
          boy[tot[t]]=true;
      }
      cin>>m;
      for(int i=1;i<=m;++i){
          string s,t;
          cin>>s>>t;
          int u=tot[s],v=tot[t];
          edge[v].pb(u);
      }
      for(int i=1;i<=id;++i){
          if(!boy[i]) continue;
          mp[mp[i]]=0;
          memset(vis,false,sizeof(vis));
          if(dfs(i)) puts("Unsafe");
          else puts("Safe");
          mp[mp[i]]=i;
      } 
      return 0;
  }
  
             

???????????????????????????????????????????? ???????????????????????????????? ???????????? ???????????????? ????????????????

???????????????????????????????? ???????? ????????????????