(未更新完、做到相关题再更新相关部分
例题:H. Mad City
利用变种拓扑排序,先把度为1的点存入队中,每次取出队头,遍历邻接点,再将该条边删除也就是将邻接点度数减一,直至队空,然后所有度数大于1的点都是在环上的点,输出即可
code
for (int i = 0; i < n; i ++ )
{
int x, y;
cin >> x >> y;
add(x, y), add(y, x);
ind[x] ++, ind[y] ++ ;
}
function<void()> topsort = [&]()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
if (ind[i] == 1) q.push(i);
while (q.size())
{
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (-- ind[v] == 1) q.push(v);
}
}
};
topsort();
for (int i = 1; i <= n; i ++ )
if (ind[i] > 1) ans = true;
利用并查集,每加一条边,判断当前这两个端点是否连通,如果不连通就把它们放到一个并查集,连通的话说明已经有别的边把这两个点连起来了,现在的这条边就是多余的,记录一下一会儿可以把这条边换掉
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool merge(int x, int y)
{
int xp = find(x), yp = find(y);
if (xp == yp) return false;
else
{
p[xp] = yp;
return true;
}
};
vector<PII> edge;
for (int i = 0; i < n - 1; i ++ )
{
int u, v;
cin >> u >> v;
if (!merge(u, v)) edge.push_back({u, v});
}
利用并查集,每加一条边,判断当前这两个端点是否连通,如果不连通就更新他们的长度和父结点情况,如果这两个端点已经连通,那么加上这一条边一定能使得形成一个环,环的长度就是两个端点距离祖先结点的和再加一
code
int find(int x)
{
if (x != fa[x])
{
int last = fa[x];
fa[x] = find(fa[x]);
dist[x] += dist[last];
}
return fa[x];
}
void func(int a, int b)
{
int aa = find(a), bb = find(b);
if (aa == bb) ans = min(ans, dist[a] + dist[b] + 1);
else
{
fa[a] = bb;
dist[a] = dist[b] + 1;
}
}
ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
func(i, x);
}