ENET - Mạng điện
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 3;
int tin[N], low[N];
bool was[N];
vector<int> a[N];
set<int> answer;
int n, m, s, t;
void visit(int u) {
was[u] = true;
for (int v : a[u]) if (!was[v]) visit(v);
}
bool sameComponent() {
visit(s);
return was[t];
}
stack<pair<int, int> > S;
int Time;
void dfs(int u, int p = 0) {
tin[u] = ++Time; low[u] = N;
for (int v : a[u]) if (v != p) {
if (tin[v]) {
low[u] = min(low[u], tin[v]);
} else {
S.push({u, v});
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= tin[u]) {
set<int> cur;
while (S.top() != make_pair(u, v)) {
cur.insert(S.top().second);
S.pop();
}
cur.insert(u); cur.insert(v); S.pop();
if (cur.count(s) && cur.count(t)) {
answer = cur;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> s >> t;
bool hasEdge = false;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
a[u].push_back(v); a[v].push_back(u);
hasEdge |= (u == s && v == t) || (u == t && v == s);
}
if (!sameComponent()) return cout << 0, 0;
if (!hasEdge) a[s].push_back(t), a[t].push_back(s);
for (int i = 1; i <= n; ++i) if (!tin[i]) dfs(i);
cout << answer.size() << endl;
for (int u : answer) cout << u << '\n';
return 0;
}