1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include <iostream> #include <cstdio> #include <stack> #include <algorithm> #define maxn 300010 #define maxm 300010 using namespace std;
int n, m, s, t;
struct Edge { int fr, to, next, w, f; } e[maxm * 2], E[maxn * 2]; int c1, head[maxn], c2, Head[maxn]; inline void add_edge(int u, int v, int w) { e[c1].fr = u; e[c1].to = v; e[c1].w = w; e[c1].next = head[u]; head[u] = c1++; }
inline void add_Edge(int u, int v, int w) { E[c2].to = v; E[c2].w = w; E[c2].next = Head[u]; Head[u] = c2++; }
int dfn[maxn], low[maxn], dcc, bl[maxn], ok[maxn]; stack<int> S; void tarjan(int u, int fa) { static int cnt = 0; dfn[u] = low[u] = ++cnt; S.push(u); for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, &f1 = e[i].f, &f2 = e[i ^ 1].f; if (v == fa) continue; if (!dfn[v]) { tarjan(v, u), low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) f1 = f2 = 1; } else low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { int t; ++dcc; do { t = S.top(); S.pop(); bl[t] = dcc; } while (t != u); } }
void dfs(int u, int fa, int f) { f |= ok[u]; if (u == t) cout << (f ? "YES" : "NO") << "\n", exit(0); for (int i = Head[u]; ~i; i = E[i].next) { int v = E[i].to, w = E[i].w; if (v == fa) continue; dfs(v, u, f | w); } }
int main() { fill(head, head + maxn, -1); fill(Head, Head + maxn, -1); ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; for (int i = 1; i <= m; ++i) { int x, y, z; cin >> x >> y >> z; add_edge(x, y, z); add_edge(y, x, z); } tarjan(1, 0); for (int i = 0; i < c1; i += 2) { int u = e[i].fr, v = e[i].to, w = e[i].w; if (bl[u] == bl[v]) ok[bl[u]] |= w; else add_Edge(bl[u], bl[v], w), add_Edge(bl[v], bl[u], w); } cin >> s >> t; s = bl[s]; t = bl[t]; dfs(s, 0, 0); return 0; }
|