【图论】判环问题

（未更新完、做到相关题再更新相关部分

无向图判断有无环并输出环上点

例题：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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

无向图判断连通分量中的多余边（即删去哪些边可以变成极大连通分量）

利用并查集，每加一条边，判断当前这两个端点是否连通，如果不连通就把它们放到一个并查集，连通的话说明已经有别的边把这两个点连起来了，现在的这条边就是多余的，记录一下一会儿可以把这条边换掉

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});
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

有向图找最小/大环

利用并查集，每加一条边，判断当前这两个端点是否连通，如果不连通就更新他们的长度和父结点情况，如果这两个端点已经连通，那么加上这一条边一定能使得形成一个环，环的长度就是两个端点距离祖先结点的和再加一

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30