Advertisement
Mirbek

6

Jun 6th, 2022
1,040
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 105;
  6.  
  7. int n, m, s, f;
  8. int used[N];
  9. vector <int> g[N];
  10.  
  11. void dfs(int v) {
  12.     used[v] = 1;
  13.     for (int u : g[v]) {
  14.         if (!used[u])
  15.             dfs(u);
  16.     }
  17. }
  18.  
  19. int main(){
  20.     cin >> n >> m >> s >> f;
  21.  
  22.     for (int i = 1; i <= m; i++) {
  23.         int u, v;
  24.         cin >> u >> v;
  25.         g[u].push_back(v);
  26.         g[v].push_back(u);
  27.     }
  28.  
  29.     dfs(s);
  30.  
  31.     vector <int> comp;
  32.  
  33.     for (int i = 1; i <= n; i++) {
  34.         if (used[i]) comp.push_back(i);
  35.     }
  36.  
  37.     int ans = n - comp.size();
  38.  
  39.     for (int c : comp) {
  40.         memset(used, 0, sizeof(used));
  41.         used[f] = 1;
  42.         dfs(c);
  43.         if (!used[s]) {
  44.             ans++;
  45.             continue;
  46.         }
  47.         memset(used, 0, sizeof(used));
  48.         used[s] = 1;
  49.         dfs(c);
  50.         if (!used[f]) {
  51.             ans++;
  52.             continue;
  53.         }
  54.         for (int d = 1; d <= n; d++) {
  55.             if (d == c || d == f || d == s) continue;
  56.             int cnt_comp = 0;
  57.             memset(used, 0, sizeof(used));
  58.             used[d] = 1;
  59.             dfs(c);
  60.             if (!used[f] && !used[s]) cnt_comp++;
  61.             memset(used, 0, sizeof(used));
  62.             used[d] = 1;
  63.             dfs(f);
  64.             if (!used[c] && !used[s]) cnt_comp++;
  65.             memset(used, 0, sizeof(used));
  66.             used[d] = 1;
  67.             dfs(s);
  68.             if (!used[f] && !used[c]) cnt_comp++;
  69.             if (cnt_comp == 3) {
  70.                 ans++;
  71.                 break;
  72.             }
  73.         }
  74.     }
  75.  
  76.     cout << ans << endl;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement