又写了一遍, 发出来做个记录
#include < cstdio > #include < algorithm > #include < iostream > using namespace std;#define N 500001 int tot = 1,
front[N],
to[N << 2],
nxt[N << 2];
int id,
dfn[N],
low[N];
int fa[N],
dep[N];
int dp[N];
int tmp[N],
q[N];
int ans;
void read(int & x) {
x = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
}
void add(int u, int v) {
to[++tot] = v;
nxt[tot] = front[u];
front[u] = tot;
to[++tot] = u;
nxt[tot] = front[v];
front[v] = tot;
}
void circle(int x, int y) {
int cnt = dep[y] - dep[x] + 1;
int now = y;
while (dfn[fa[now]] >= dfn[x]) tmp[cnt--] = now,
now = fa[now];
tmp[cnt] = now;
cnt = dep[y] - dep[x] + 1;
int nn = cnt;
for (int i = 1; i <= cnt; ++i) tmp[++nn] = tmp[i];
int h = 0,
t = 0;
for (int i = 1; i <= nn; ++i) {
while (h < t && i - q[h] > cnt / 2) h++;
if (h < t) ans = max(ans, dp[tmp[q[h]]] + dp[tmp[i]] + i - q[h]);
while (h < t && dp[tmp[i]] - i > dp[tmp[q[t - 1]]] - q[t - 1]) t--;
q[t++] = i;
}
for (int i = 2; i <= cnt; ++i) dp[x] = max(dp[x], dp[tmp[i]] + min(i - 1, cnt - i + 1));
}
void tarjan(int x, int y) {
dfn[x] = low[x] = ++id;
int t;
for (int i = front[x]; i; i = nxt[i]) {
if (i == (y ^ 1)) continue;
t = to[i];
if (!dfn[t]) {
fa[t] = x;
dep[t] = dep[x] + 1;
tarjan(t, i);
low[x] = min(low[x], low[t]);
} else low[x] = min(low[x], dfn[t]);
if (dfn[x] < low[t]) {
ans = max(ans, dp[x] + dp[t] + 1);
dp[x] = max(dp[x], dp[t] + 1);
}
}
for (int i = front[x]; i; i = nxt[i]) {
if (i == (y ^ 1)) continue;
t = to[i];
if (fa[t] != x && dfn[x] < dfn[t]) circle(x, t);
}
}
int main() {
int n,
m;
read(n);
read(m);
int k,
x,
last;
while (m--) {
read(k);
read(last);
while (--k) {
read(x);
add(last, x);
last = x;
}
}
tarjan(1, 0);
printf("%d", ans);
}
来源: http://www.bubuko.com/infodetail-2484138.html