CF923(Div. 3)-F Microcycle
(Test/CF/CF923-F.test.cpp)

• View this file on GitHub
• Last update: 2025-06-09 10:00:52+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://codeforces.com/contest/1927/problem/F
• Link: https://codeforces.com/contest/1927/submission/323560243

無向グラフ上の辺 $\{ u, v \}$ が橋でない -> $\{ u, v \}$ を含むサイクルが存在する。

サイクルがあるとわかっているなら、単純に $\{ u, v \}$ を除去した上で $u-v$ パスを発見する問題に帰着する。

Depends on

• Lowlink (橋・関節点) (Src/Graph/Components/Lowlink.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

// #define PROBLEM "https://codeforces.com/contest/1927/problem/F"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Graph/Components/Lowlink.hpp"

using namespace zawa;

#include <iostream>
#include <tuple>
#include <vector>

/*
 * Codeforces Round 923 (Div. 3) - F Microcycle
 * https://codeforces.com/contest/1927/submission/323560243
 */

void solve() {
    int t; std::cin >> t;
    while (t--) {
        int n, m; std::cin >> n >> m;
        std::vector<std::tuple<int, int, int>> e(m);
        Lowlink low(n);
        for (auto& [u, v, w] : e) {
            std::cin >> u >> v >> w;
            u--; v--;
            low.addEdge(u, v);
        }
        auto info{low.build()};
        int ans{(int)1e9}, ansId{-1};
        for (int i{} ; i < m ; i++) {
            if (info.isBridge(i)) continue;
            if (ans > std::get<2>(e[i])) {
                ans = std::get<2>(e[i]);
                ansId = i;
            }
        }
        std::vector<int> path;
        std::vector<bool> vis(n);
        auto dfs{[&](auto dfs, int v) -> bool {
            vis[v] = true;
            if (v == std::get<1>(e[ansId])) {
                path.push_back(v + 1);
                return true;
            }
            for (auto [x, i] : low[v]) {
                if ((int)i == ansId) continue;
                if (vis[x]) continue;
                if (dfs(dfs, x)) {
                    path.push_back(v + 1);
                    return true;
                }
            }
            return false;
        }};
        assert(dfs(dfs, std::get<0>(e[ansId])));
        std::cout << ans << ' ' << path.size() << '\n';
        for (int i{} ; i < (int)path.size() ; i++) {
            std::cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}

#line 1 "Test/CF/CF923-F.test.cpp"
// #define PROBLEM "https://codeforces.com/contest/1927/problem/F"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Graph/Components/Lowlink.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Components/Lowlink.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Lowlink {
public:

    using V = usize;

    using ID = usize;

private:

    class LowlinkResponse {
    public:

        LowlinkResponse() = default;

        LowlinkResponse(std::vector<u32>&& articulation, std::vector<bool>&& bridge)
            : articulation_{std::move(articulation)}, bridge_{std::move(bridge)} {}

        inline bool isArticulation(V v) const {
            assert(v < articulation_.size());
            return articulation_[v] > 1u;
        }

        inline u32 cut(V v) const {
            assert(v < articulation_.size());
            return articulation_[v];
        }

        inline bool isBridge(ID i) const {
            assert(i < bridge_.size());
            return bridge_[i];
        }

    private:

        std::vector<u32> articulation_;

        std::vector<bool> bridge_;

    };

    static constexpr usize INVALID{static_cast<usize>(-1)};

    usize n_{}, m_{};

    std::vector<std::vector<std::pair<V, ID>>> g_;

    std::vector<std::pair<V, V>> e_;

    void dfs(V v, V p, u32& t, std::vector<u32>& articulation, 
            std::vector<bool>& bridge, std::vector<usize>& in, std::vector<usize>& low) const {
        low[v] = in[v] = t++;
        u32 deg{}; 
        for (const auto& [x, i] : g_[v]) {
            if (in[x] == INVALID) {
                deg++;
                dfs(x, v, t, articulation, bridge, in, low);
                low[v] = std::min(low[v], low[x]);
                if (p != INVALID and low[x] >= in[v]) {
                    articulation[v]++;
                }
                if (low[x] > in[v]) {
                    bridge[i] = true;
                }
            }
            else if (x != p) {
                low[v] = std::min(low[v], in[x]);
            }
        }
        if (p == INVALID) {
            articulation[v] = deg;
        }
    }

public:

    constexpr usize size() const noexcept {
        return n_;
    }

    constexpr usize edgeSize() const noexcept {
        return m_;
    }

    Lowlink() = default;

    explicit Lowlink(usize n) 
        : n_{n}, m_{}, g_(n) {
        g_.shrink_to_fit();
    }
    
    ID addEdge(V u, V v) {
        ID res{m_++};
        e_.emplace_back(u, v);
        g_[u].emplace_back(v, res);
        g_[v].emplace_back(u, res);
        return res;
    }

    const std::vector<std::pair<V, ID>>& operator[](V v) const noexcept {
        assert(v < size());
        return g_[v];
    }
    const std::pair<V, V>& edge(ID i) const noexcept {
        assert(i < edgeSize());
        return e_[i];
    }

    LowlinkResponse build() const {
        u32 t{};
        std::vector<u32> articulation(size(), 1u);
        std::vector<usize> in(size(), INVALID), low(size());
        std::vector<bool> bridge(edgeSize());
        for (u32 v{} ; v < size() ; v++) if (in[v] == INVALID) {
            dfs(v, INVALID, t, articulation, bridge, in, low);
        }
        return LowlinkResponse{ std::move(articulation), std::move(bridge) };
    }

};

} // namespace zawa
#line 5 "Test/CF/CF923-F.test.cpp"

using namespace zawa;

#include <iostream>
#include <tuple>
#line 11 "Test/CF/CF923-F.test.cpp"

/*
 * Codeforces Round 923 (Div. 3) - F Microcycle
 * https://codeforces.com/contest/1927/submission/323560243
 */

void solve() {
    int t; std::cin >> t;
    while (t--) {
        int n, m; std::cin >> n >> m;
        std::vector<std::tuple<int, int, int>> e(m);
        Lowlink low(n);
        for (auto& [u, v, w] : e) {
            std::cin >> u >> v >> w;
            u--; v--;
            low.addEdge(u, v);
        }
        auto info{low.build()};
        int ans{(int)1e9}, ansId{-1};
        for (int i{} ; i < m ; i++) {
            if (info.isBridge(i)) continue;
            if (ans > std::get<2>(e[i])) {
                ans = std::get<2>(e[i]);
                ansId = i;
            }
        }
        std::vector<int> path;
        std::vector<bool> vis(n);
        auto dfs{[&](auto dfs, int v) -> bool {
            vis[v] = true;
            if (v == std::get<1>(e[ansId])) {
                path.push_back(v + 1);
                return true;
            }
            for (auto [x, i] : low[v]) {
                if ((int)i == ansId) continue;
                if (vis[x]) continue;
                if (dfs(dfs, x)) {
                    path.push_back(v + 1);
                    return true;
                }
            }
            return false;
        }};
        assert(dfs(dfs, std::get<0>(e[ansId])));
        std::cout << ans << ' ' << path.size() << '\n';
        for (int i{} ; i < (int)path.size() ; i++) {
            std::cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}

Back to top page