5665 | 2023. 09. 05 00:23:41 | TomaSajt | Kaktuszgráf | cpp17 | Elfogadva 50/50 | 3ms | 4524 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<array<int, 2>>> g;
vector<int> l, d;
int ts = 0;
stack<int> st;
vector<int> comp_sizes;
// components are separated by cutting vertices
void make_comps(int u, int par_ei) {
d[u] = l[u] = ++ts;
int ch = 0;
for (auto& [v, ei] : g[u]) {
if (ei == par_ei) continue; // case: tree-edge, from the other direction
if (d[v] > d[u]) continue; // case: back-edge, from the other direction
st.push(ei);
if (d[v] != 0) {
// case: (u,v) is back-edge
l[u] = min(l[u], d[v]);
continue;
}
// case: (u,v) is tree-edge
ch++;
make_comps(v, ei);
l[u] = min(l[u], l[v]);
if ((par_ei == -1 && ch > 1) || (l[v] >= d[u])) {
// case: u is a cutting vertex
comp_sizes.push_back(0);
while (st.top() != ei) {
comp_sizes.back()++;
st.pop();
}
comp_sizes.back()++;
st.pop();
}
}
}
int main() {
cin.tie(0), ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
g.resize(n + 1);
for (int ei = 0; ei < m; ei++) {
int u, v;
cin >> u >> v;
g[u].push_back({v, ei});
g[v].push_back({u, ei});
}
l.resize(n + 1), d.resize(n + 1);
make_comps(1, -1);
comp_sizes.back() += st.size();
cout << *max_element(comp_sizes.begin(), comp_sizes.end());
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1832 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2224 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2448 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2368 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2644 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2856 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3116 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3284 KiB | |||
9 | Elfogadva | 2/2 | 3ms | 3496 KiB | |||
10 | Elfogadva | 2/2 | 3ms | 3704 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3664 KiB | |||
12 | Elfogadva | 2/2 | 3ms | 3924 KiB | |||
13 | Elfogadva | 2/2 | 3ms | 3852 KiB | |||
14 | Elfogadva | 2/2 | 3ms | 3812 KiB | |||
15 | Elfogadva | 2/2 | 3ms | 3964 KiB | |||
16 | Elfogadva | 2/2 | 3ms | 3860 KiB | |||
17 | Elfogadva | 2/2 | 3ms | 4076 KiB | |||
18 | Elfogadva | 2/2 | 3ms | 4292 KiB | |||
19 | Elfogadva | 3/3 | 3ms | 4296 KiB | |||
20 | Elfogadva | 3/3 | 3ms | 4452 KiB | |||
21 | Elfogadva | 3/3 | 3ms | 4492 KiB | |||
22 | Elfogadva | 3/3 | 3ms | 4524 KiB | |||
23 | Elfogadva | 3/3 | 3ms | 4512 KiB | |||
24 | Elfogadva | 3/3 | 3ms | 4508 KiB |