牛客多校第六场反思

D. Puzzle: Wagiri

题目大意

1. 给定一张简单连通无向图，边有黑白
2. 移除任意一条边使得图仍然连通，且黑边都在环上，白边都不在环上，或者输出无解

思路

1. 黑边的环在一开始就存在了
2. 可以先不看白边，反正是可以移除的
3. 把黑边缩点，然后用一个把割边去掉，再用白边连就好了，白边不够就无解了
4. 注意：这里割边也是要删除的边
5. 对白边的处理：如果连接白边的两个点都连了同一个边双，那这个白边就不能再被用了，否则就可以用它来连，就有一条白边可以用了
6. 具体的步骤：

• 对黑边求一个边双连通分量，然后把割边去除
• 可以用并查集把所有点连起来，最后删边剩下的结果应该也是之剩下一个连通块
• 如果白边不够，最后肯定剩下不止一个连通块，就无解了

代码

#include <bits/stdc++.h>
// lun --> 黑边  qie --> 白边
const int maxn = 100005;
int head[maxn], low[maxn], dfn[maxn], left[maxn], right[maxn], pre[maxn], ans[maxn];
bool white[maxn], vis[maxn], ifcut[maxn * 4]; // 是否为割边
int n = 0, m = 0, cnt = 1, u = 0, v = 0, tmp = 0, num = 0;
std::string s;

int find(int x)
{
    if (x == pre[x]) return x;
    return pre[x] = find(pre[x]);
}

struct Edge
{
    int start;
    int terminus;
    int id;
    int next;
}edge[maxn * 4];

void AddEdge(int start, int terminus, int id)
{
    edge[++cnt].start = start;
    edge[cnt].terminus = terminus;
    edge[cnt].id = id;
    edge[cnt].next = head[start];
    head[start] = cnt;
}


void tarjan(int x, int fa)
{
    low[x] = dfn[x] = ++tmp;
    for (int i = head[x]; i != -1; i = edge[i].next)
    {
        int j = edge[i].terminus;
        if (j == fa) continue;
        if (dfn[j] == 0)
        {
            tarjan(j, x);
            low[x] = std::min(low[x], low[j]);
            if (dfn[x] < low[j]) // 如果是割边的话
            {
                ifcut[i] = ifcut[i ^ 1] = true;
            }  
        }
        else
        {
            low[x] = std::min(low[x], dfn[j]);
        }
    }
}
// dfs把割边给去除了
void dfs(int x)
{
    vis[x] = 1;
    for (int i = head[x]; i != -1; i = edge[i].next)
    {
        int j = edge[i].terminus;
        if (ifcut[i] || vis[j]) continue;
        dfs(j);
        pre[find(x)] = find(j);
    }
}

int main()
{
    
    std::cin >> n >> m;
    for (int i = 0; i <= n; i++)
    {
        head[i] = -1;
        pre[i] = i;
    }

    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v >> s;
        left[i] = u, right[i] = v;
        if (s == "Lun")
        {
            AddEdge(u, v, i);
            AddEdge(v, u, i);
        }
        else
        {
            white[i] = 1;
        }
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            tarjan(i, -1);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0) 
        {
            dfs(i);
        }
    }

    for (int i = 2; i <= cnt; i += 2) // i += 2的原因是这个是无向图，i 和 i + 1是一条边
    {
        if (!ifcut[i])
        {
            ans[++num] = edge[i].id;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        if (white[i])
        {
            int prea = find(left[i]), preb = find(right[i]);
            if (prea == preb) continue;
            pre[prea] = preb;
            ans[++num] = i;
        }
    }

    int anc = 0;
    for (int i = 1; i <= n; i++)
    {
        if (pre[i] == i)
        {
            anc++;
        }
    }
    if (anc > 1)
    {
        std::cout << "NO" << '\n';
        return 0;
    }
    std::cout << "YES" << '\n';
    std::cout << num << '\n';
    for (int i = 1; i <= num; i++)
    {
        std::cout << left[ans[i]] << " " << right[ans[i]] << '\n';
    }
    return 0;
}