Submission #371593

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;

const int MAXN = 100100;
vector<int> G[MAXN];
int n;
int loop = 0;

int state[MAXN]; // 1がまだdfsフェイズのやつ 2がすでに探索済み
int depth[MAXN];

void dfs(int v, int p, int d) {
//    cout << v << "  " << d<< endl;
    depth[v] = d;
    state[v] = 1;
    for (int el : G[v]) {
        if (state[el] == 2 || el == p) continue;
        if (state[el] == 1) {
            loop = depth[v] - depth[el] + 1;
//            cout << "発見!!" << endl;
//            cout << "いま: " << v << " みつけた: " << el << endl;
            state[v] = 2;
            return;
        }
        dfs(el, v, d+1);
    }
    state[v] = 2;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int mi = MAXN;
    for (int i = 0; i < n; i++) mi = min(mi, (int)G[i].size());
    dfs(0, -1, 0);
    printf("%d %d\n", mi, (loop/2)*2+(n-loop));
    return 0;
}

Submission Info

Judge Result