Submission #43366069

---

Source Code Expand

import std;

void read(T...)(string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

void main () {
    int N1, N2, M; readln.read(N1, N2, M);
    int[][] graph = new int[][](N1+N2, 0);

    foreach (_; 0..M) {
        int a, b; readln.read(a, b);
        a--, b--;
        graph[a] ~= b;
        graph[b] ~= a;
    }
    solve(N1, N2, M, graph);
}

void solve (int N1, int N2, int M, int[][] graph) {
    // 選ぶ頂点は 1 <= u <= N1 と N1+1 <= v <= N1+N2 なことに注意

    int[] visited = new int[](N1+N2);
    DList!int Q;
    { // 頂点1からの連結成分の調査
        visited[] = -1;
        visited[0] = 0;
        Q.insert(0);
        while (!Q.empty) {
            auto begin = Q.front; Q.removeFront;
            foreach (to; graph[begin]) {
                if (visited[to] == -1) {
                    visited[to] = visited[begin] + 1;
                    Q.insert(to);
                }
            }
        }
    }

    // 頂点uを選ぶ
    import std.algorithm : reduce;
    int u = reduce!(max)(visited[0..N1]);

    { // 頂点N1+N2からの連結成分の調査
        visited[] = -1;
        visited[N1+N2-1] = 0;
        Q.insert(N1+N2-1);
        while (!Q.empty) {
            auto begin = Q.front; Q.removeFront;
            foreach (to; graph[begin]) {
                if (visited[to] == -1) {
                    visited[to] = visited[begin] + 1;
                    Q.insert(to);
                }
            }
        }
    }

    // 頂点vを選ぶ
    int v = reduce!(max)(visited[N1..$]);

    writeln(u+v+1);
}

Submission Info

Judge Result