652E - Pursuit For Artifacts - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 312345;
int compid;

vector<vector<pair<int, int>>> g(MAX);

vector<pair<int, int>> edges(MAX);

vector<bool> bridges(MAX, false);
vector<bool> artifacts(MAX, false);
vector<bool> artifactsComp(MAX, false);

vector<vector<pair<int, int>>> cond(MAX);

int n, m; 

// marcos pontes

vector<bool> visited(MAX, false);
vector<int> tin(MAX), low(MAX);
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (auto to : g[v]) {
        if (to.first == p) continue;
        if (visited[to.first]) {
            low[v] = min(low[v], tin[to.first]);
        } else {
            dfs(to.first, v);
            low[v] = min(low[v], low[to.first]);
            if (low[to.first] > tin[v]){
                bridges[to.second] = true;
            }   
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]){
            dfs(i);
        }
    }
}

vector<bool> used(MAX, false);
vector<int> comp(MAX, -1);

// marcos componentes
void dfs1(int v, int p) {
    used[v] = true;
    comp[v] = compid;
    // cout << "vertice " <<  v << endl;
    for(auto &e: g[v]) {
        int to, id;
        tie(to, id) = e;
        
        if(bridges[id]) { // avoid traversing from this edge. so we get full component.
            continue;
        }

        if (artifacts[id]){
            artifactsComp[compid] = true;
        }

        if(used[to]) {
            continue;
        }
        // cout << id << " " << compid << endl;

        dfs1(to, v);
    }
}

vector<int> visited2(MAX, 0);
bool foundArtifact = false;
bool dfs2(int fr, int to){
    if (visited2[fr])
        return false;
    if (fr == to){
        foundArtifact = foundArtifact || artifactsComp[to];
        return true;
    }
    visited2[fr] = 1;

    bool ans = false;
    for (auto &e : cond[fr]){
        int v, id;
        tie(v, id) = e;

        if (dfs2(v, to)){
            ans = true;
            foundArtifact = foundArtifact || artifacts[id];
            foundArtifact = foundArtifact || artifactsComp[fr];
        }
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
        edges[i].first = x;
        edges[i].second = y;
        if (z) artifacts[i] = true;
    }

    find_bridges();
    compid = 0;
    for (int i = 0; i < n; ++i){
        if (comp[i] == -1){
            dfs1(i, -1);
            compid++;
        }
    }

    for (int i = 0; i < m; ++i){
        if (!bridges[i]) continue;
        int a, b;
        a = edges[i].first;
        b = edges[i].second;
        cond[comp[a]].push_back({comp[b], i});
        cond[comp[b]].push_back({comp[a], i});
        // cout << i << " " << artifacts[i] << endl;
    }

    int a1, b1;
    cin >> a1 >> b1;
    a1--; b1--;
    // cout << comp[a1] << " " << comp[b1] << endl;
    dfs2(comp[a1], comp[b1]);

    // int i = 0; 
    // while (cond[i].size()){
    //     cout << artifactsComp[i] << " ";
    //     i++;
    // }
    // cout << endl;

    // for (int i = 0; i < m; ++i){
    //     cout << artifacts[i] << " ";
    // }
    // cout << endl;

    if (foundArtifact)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;


    return 0;
}