UVa

UVa00539 POJ2258 ZOJ1947 The Settlers of Catan

題目連結 UVa
題目連結 POJ
題目連結 ZOJ

  • 題意：給定一張 $N$ 個點 $M$ 條邊的圖，問圖上最長不重複的路徑。
  • 題解：DFS，每遇到一個點就紀錄拜訪過，離開的時候取消紀錄，接著走其他沒被記錄走過的點，在 DFS 途中更新答案。
    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
    71
    #include <cstring>
    #include <iostream>
    #include <vector>

    using namespace std;
    const int N = 30;
    struct Edge
    {
        Edge(){};
        Edge(int _from, int _to) : from(_from), to(_to) {}
        int from, to;
    };
    int ans;
    bool vis[N];
    vector<Edge> E;
    vector<int> G[N];

    void init()
    {
        E.clear();
        for (int i = 0; i < N; i++)
        {
            G[i].clear();
        }
    }

    void add_Edge(int from, int to)
    {
        G[from].push_back(E.size());
        G[to].push_back(E.size());
        E.push_back(Edge(from, to));
    }

    void dfs(int s, int d)
    {
        ans = max(ans, d);
        for (int i = 0; i < (int)G[s].size(); ++i)
        {
            int it = G[s][i];
            if (vis[it])
                continue;
            vis[it] = true;
            Edge &e = E[it];
            dfs(s ^ e.from ^ e.to, d + 1);
            vis[it] = false;
        }
    }

    int main()
    {
        cin.tie(NULL);
        cout.tie(NULL);
        ios_base::sync_with_stdio(false);
        int n, m;
        while (cin >> n >> m, n || m)
        {
            init();
            for (int i = 0, x, y; i < m; i++)
            {
                cin >> x >> y;
                add_Edge(x, y);
            }
            ans = 0;
            for (int i = 0; i < n; i++)
            {
                memset(vis, 0, sizeof(vis));
                dfs(i, 0);
            }
            cout << ans << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts