DuongNhi99

ENET

Dec 9th, 2020 (edited)
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2005;
  5.  
  6. int n, m, s, t;
  7. vector<int> a[N];
  8. int ans;
  9. int isCut[N], child[N], ok[N], vs[N];
  10. int step;
  11. int low[N], num[N], d[N], e[N];
  12.  
  13. void visit(int u) {
  14.     low[u] = num[u] = ++step;
  15.  
  16.     for(int v : a[u]) {
  17.         if(v == d[u]) continue;
  18.  
  19.         if(num[v])
  20.             low[u] = min(low[u], num[v]);
  21.         else {
  22.             d[v] = u;
  23.             visit(v);
  24.             low[u] = min(low[u], low[v]);
  25.         }
  26.     }
  27. }
  28.  
  29. void bfs(int u, int pa, int d[]) {
  30.     queue<int> q;
  31.     fill(d + 1, d + n + 1, 0);
  32.     d[u] = d[pa] = 1;
  33.     q.push(u);
  34.  
  35.     if(u == pa) return;
  36.  
  37.     while(!q.empty()) {
  38.         u = q.front();
  39.         q.pop();
  40.  
  41.         for(int v : a[u]) {
  42.             if(d[v]) continue;
  43.             d[v] = 1;
  44.             q.push(v);
  45.         }
  46.     }
  47. }
  48.  
  49. int connected(int u, int v) {
  50.     vs[u] = 1;
  51.     if(u == v) return 1;
  52.  
  53.     for(int uv : a[u])
  54.         if(!vs[uv] && connected(uv, v))
  55.             return 1;
  56.  
  57.     return 0;
  58. }
  59.  
  60. int main() {
  61.     //freopen("in.txt", "r", stdin);
  62.     freopen("ENET.inp", "r", stdin);
  63.     freopen("ENET.out", "w", stdout);
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL); cout.tie(NULL);
  66.  
  67.     cin >> n >> m >> s >> t;
  68.     for(int i = 1; i <= m; i++) {
  69.         int x, y; cin >> x >> y;
  70.         a[x].push_back(y);
  71.         a[y].push_back(x);
  72.     }
  73.  
  74.     if(!connected(s, t)) {
  75.         cout << 0 << '\n';
  76.         return 0;
  77.     }
  78.  
  79.     for(int i = 1; i <= n; i++)
  80.         if(!d[i]) visit(i);
  81.  
  82.     for(int i = 1; i <= n; i++)
  83.         child[d[i]]++;
  84.  
  85.     for(int i = 1; i <= n; i++)
  86.         if(d[i] && !isCut[d[i]])
  87.             if(low[i] >= num[d[i]] && (d[d[i]] || child[d[i]] > 1))
  88.                 isCut[d[i]] = 1;
  89.     fill(ok + 1, ok + n + 1, 1);
  90.  
  91.     for(int i = 1; i <= n; i++)
  92.         if(isCut[i]) {
  93.             bfs(s, i, d);
  94.             bfs(t, i, e);
  95.  
  96.             for(int j = 1; j <= n; j++)
  97.                 ok[j] &= (d[j] | e[j]);
  98.         }
  99.  
  100.     for(int i = 1; i <= n; i++)
  101.         ans += ok[i];
  102.  
  103.     cout << ans << '\n';
  104.  
  105.     vector<int> res;
  106.     for(int i = 1; i <= n; i++)
  107.         if(ok[i])  cout << i << '\n';
  108.  
  109.     return 0;
  110. }
  111.  
Add Comment
Please, Sign In to add comment