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;
}

Download