Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2005;
- int n, m, s, t;
- vector<int> a[N];
- int ans;
- int isCut[N], child[N], ok[N], vs[N];
- int step;
- int low[N], num[N], d[N], e[N];
- void visit(int u) {
- low[u] = num[u] = ++step;
- for(int v : a[u]) {
- if(v == d[u]) continue;
- if(num[v])
- low[u] = min(low[u], num[v]);
- else {
- d[v] = u;
- visit(v);
- low[u] = min(low[u], low[v]);
- }
- }
- }
- void bfs(int u, int pa, int d[]) {
- queue<int> q;
- fill(d + 1, d + n + 1, 0);
- d[u] = d[pa] = 1;
- q.push(u);
- if(u == pa) return;
- while(!q.empty()) {
- u = q.front();
- q.pop();
- for(int v : a[u]) {
- if(d[v]) continue;
- d[v] = 1;
- q.push(v);
- }
- }
- }
- int connected(int u, int v) {
- vs[u] = 1;
- if(u == v) return 1;
- for(int uv : a[u])
- if(!vs[uv] && connected(uv, v))
- return 1;
- return 0;
- }
- int main() {
- //freopen("in.txt", "r", stdin);
- freopen("ENET.inp", "r", stdin);
- freopen("ENET.out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(NULL); cout.tie(NULL);
- cin >> n >> m >> s >> t;
- for(int i = 1; i <= m; i++) {
- int x, y; cin >> x >> y;
- a[x].push_back(y);
- a[y].push_back(x);
- }
- if(!connected(s, t)) {
- cout << 0 << '\n';
- return 0;
- }
- for(int i = 1; i <= n; i++)
- if(!d[i]) visit(i);
- for(int i = 1; i <= n; i++)
- child[d[i]]++;
- for(int i = 1; i <= n; i++)
- if(d[i] && !isCut[d[i]])
- if(low[i] >= num[d[i]] && (d[d[i]] || child[d[i]] > 1))
- isCut[d[i]] = 1;
- fill(ok + 1, ok + n + 1, 1);
- for(int i = 1; i <= n; i++)
- if(isCut[i]) {
- bfs(s, i, d);
- bfs(t, i, e);
- for(int j = 1; j <= n; j++)
- ok[j] &= (d[j] | e[j]);
- }
- for(int i = 1; i <= n; i++)
- ans += ok[i];
- cout << ans << '\n';
- vector<int> res;
- for(int i = 1; i <= n; i++)
- if(ok[i]) cout << i << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment