9956 | 2024. 03. 21 15:55:08 | kukkerman | Kaktuszgráf | cpp17 | Elfogadva 50/50 | 4ms | 4512 KiB |
#include <iostream>
#include <vector>
using Graf = std::vector<std::vector<int>>;
Graf beolvas(std::istream &be) {
int n, m;
be >> n >> m;
Graf g(n);
for (auto i = 0; i < m; i++) {
int a, b;
be >> a >> b;
--a;
--b;
g[a].push_back(b);
g[b].push_back(a);
}
return g;
}
int max_kor_hossza(int u, const Graf &g, std::vector<int> &tav) {
int h = 0;
for (auto v: g[u]) {
if (tav[v] == -1) {
tav[v] = tav[u] + 1;
h = std::max(h, max_kor_hossza(v, g, tav));
} else if (tav[v] - tav[u] > 1) {
h = std::max(h, tav[v] - tav[u] + 1);
}
}
return h;
}
int feldolgoz(const Graf &g) {
const auto n = g.size();
std::vector<int> tav(n, -1);
tav[0] = 0;
return max_kor_hossza(0, g, tav);
}
int main() {
const auto g = beolvas(std::cin);
std::cout << feldolgoz(g) << '\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2096 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2436 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2408 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2676 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2652 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2952 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3212 KiB | |||
9 | Elfogadva | 2/2 | 3ms | 3432 KiB | |||
10 | Elfogadva | 2/2 | 3ms | 3332 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3596 KiB | |||
12 | Elfogadva | 2/2 | 3ms | 3664 KiB | |||
13 | Elfogadva | 2/2 | 3ms | 3676 KiB | |||
14 | Elfogadva | 2/2 | 3ms | 3584 KiB | |||
15 | Elfogadva | 2/2 | 3ms | 3852 KiB | |||
16 | Elfogadva | 2/2 | 3ms | 3768 KiB | |||
17 | Elfogadva | 2/2 | 3ms | 3788 KiB | |||
18 | Elfogadva | 2/2 | 3ms | 3800 KiB | |||
19 | Elfogadva | 3/3 | 3ms | 3824 KiB | |||
20 | Elfogadva | 3/3 | 3ms | 3876 KiB | |||
21 | Elfogadva | 3/3 | 4ms | 4176 KiB | |||
22 | Elfogadva | 3/3 | 3ms | 4260 KiB | |||
23 | Elfogadva | 3/3 | 3ms | 4512 KiB | |||
24 | Elfogadva | 3/3 | 3ms | 4492 KiB |