贝壳B题
B题是 双联通分量，用Tarjan扫一遍，重新建图然后减掉最深的两条路径
void tarjan(int u, int pre) //Tarjan强连通
{
vis[u] = true;
dfn[u] = low[u] = ++dep;
st.push(u);
fa[u] = true;
for (int i = s[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].v;
if (edge[i].flag == false)
continue;
edge[i].flag = edge[i ^ 1].flag = false;
if (!vis[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (dfn[u]<low[v])
{
bridge[bri_cnt][0] = u;
bridge[bri_cnt++][1] = v;
}
}
else if (fa[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int t;
do
{
id[t = st.top()] = res;
st.pop();
fa[t] = false;
} while (t != u);
res++;
}
}
int dfs(int u, int pre) //扫最长的路径
{
int tmp = 0;
for (int i = s[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].v;
if (v == pre) continue;
int d = dfs(v, u);
pre_d = max(pre_d, tmp + d);
tmp = max(tmp, d);
}
return tmp + 1;
}
#贝壳找房#{
vis[u] = true;
dfn[u] = low[u] = ++dep;
st.push(u);
fa[u] = true;
for (int i = s[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].v;
if (edge[i].flag == false)
continue;
edge[i].flag = edge[i ^ 1].flag = false;
if (!vis[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (dfn[u]<low[v])
{
bridge[bri_cnt][0] = u;
bridge[bri_cnt++][1] = v;
}
}
else if (fa[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int t;
do
{
id[t = st.top()] = res;
st.pop();
fa[t] = false;
} while (t != u);
res++;
}
}
int dfs(int u, int pre) //扫最长的路径
{
int tmp = 0;
for (int i = s[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].v;
if (v == pre) continue;
int d = dfs(v, u);
pre_d = max(pre_d, tmp + d);
tmp = max(tmp, d);
}
return tmp + 1;
}
查看21道真题和解析
