Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 105;
- int n, m, s, f;
- int used[N];
- vector <int> g[N];
- void dfs(int v) {
- used[v] = 1;
- for (int u : g[v]) {
- if (!used[u])
- dfs(u);
- }
- }
- int main(){
- cin >> n >> m >> s >> f;
- for (int i = 1; i <= m; i++) {
- int u, v;
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- dfs(s);
- vector <int> comp;
- for (int i = 1; i <= n; i++) {
- if (used[i]) comp.push_back(i);
- }
- int ans = n - comp.size();
- for (int c : comp) {
- memset(used, 0, sizeof(used));
- used[f] = 1;
- dfs(c);
- if (!used[s]) {
- ans++;
- continue;
- }
- memset(used, 0, sizeof(used));
- used[s] = 1;
- dfs(c);
- if (!used[f]) {
- ans++;
- continue;
- }
- for (int d = 1; d <= n; d++) {
- if (d == c || d == f || d == s) continue;
- int cnt_comp = 0;
- memset(used, 0, sizeof(used));
- used[d] = 1;
- dfs(c);
- if (!used[f] && !used[s]) cnt_comp++;
- memset(used, 0, sizeof(used));
- used[d] = 1;
- dfs(f);
- if (!used[c] && !used[s]) cnt_comp++;
- memset(used, 0, sizeof(used));
- used[d] = 1;
- dfs(s);
- if (!used[f] && !used[c]) cnt_comp++;
- if (cnt_comp == 3) {
- ans++;
- break;
- }
- }
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement