P3731 [HAOI2017]新型城市化

保证原图补图是个二分图，在原图中加入一条边能使原图最大团数至少加一的边有哪些。

就是寻找二分图必须边。

对于补图用网络流跑最大匹配，残余网络再跑$tarjan$（即满流的边不能走，$tarjan$可走反边）

• 如果出现增广环，显然可以将流量选择一下，出现新的匹配

对于补图的某条边，它是必须边的条件是

• 两个端点在不同的强连通分量里
• 网络流的残余网络里正边流满
• 不是源点和汇点。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

struct Edge
{
    int to, w, nxt;
    Edge() {}
    Edge(int v, int c, int t) : to(v), w(c), nxt(t) {}
};
const int EN = 2e5 + 10;
const int EM = 1e6 + 10;
struct Dinic
{

    Edge e[EM << 1];
    int head[EN], scnt, d[EN], cur[EN];
    pii pre[EN];
    Dinic() { scnt = 1; }
    void addEdge(int u, int v, int w)
    {
        e[++scnt] = Edge(v, w, head[u]);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v]);
        head[v] = scnt;
    }
    bool bfs(int s, int t)
    {
        queue<int> q;
        memset(d, 0, sizeof(d));
        q.push(s);
        d[s] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;
                if (!d[to] && e[i].w)
                {
                    d[to] = d[x] + 1;
                    q.push(to);
                    if (to == t)
                        return true;
                }
            }
        }
        return false;
    }
    ll dfs(int x, int t, int flow)
    {
        if (x == t)
            return flow;
        ll res = 0;
        for (int i = cur[x]; i; i = e[i].nxt)
        {
            cur[x] = i;
            int to = e[i].to;
            if (d[to] == d[x] + 1 && e[i].w)
            {
                int dis = dfs(to, t, min(flow, e[i].w));
                if (dis)
                {
                    e[i].w -= dis;
                    e[i ^ 1].w += dis;
                    flow -= dis;
                    res += dis;
                    if (!flow)
                        return res;
                }
            }
        }
        return res;
    }
    ll Maxflow(int s, int t)
    {
        ll ans = 0;
        while (bfs(s, t))
        {
            memcpy(cur, head, sizeof(head));
            ans += dfs(s, t, INF);
        }
        return ans;
    }
} dc;

namespace tarjan
{
    vector<int> g[N];
    stack<int> s;
    int n, m;
    int dfn[N], be[N], low[N], ln, vis[N], gcnt;
    void addEdge(int u, int v)
    {
        g[u].push_back(v);
    }
    void dfs(int x)
    {

        dfn[x] = low[x] = ++gcnt;
        vis[x] = 1;
        s.push(x);
        for (int i = 0; i < g[x].size(); i++)
        {
            int to = g[x][i];
            if (!dfn[to])
            {
                dfs(to);
                low[x] = min(low[x], low[to]);
            }
            else if (vis[to])
            {
                low[x] = min(low[x], dfn[to]);
            }
        }
        int cur;
        if (dfn[x] == low[x])
        {
            ln++;
            do
            {
                cur = s.top();
                s.pop();
                vis[cur] = 0;
                be[cur] = ln;
            } while (cur != x);
        }
    }
    void solve(int n)
    {
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                dfs(i);
    }
} // namespace tarjan

vector<int> g[N];
int vis[N], col[N];
void dfs(int x, int co)
{
    col[x] = co;
    vis[x] = 1;
    for (int to : g[x])
    {
        if (!vis[to])
            dfs(to, co ^ 1);
    }
}

int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    int s = n + 1, t = n + 2;

    for (int i = 1; i <= n; i++)
    {
        if (!col[i])
            dc.addEdge(s, i, 1);
        else
            dc.addEdge(i, t, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!col[i])
        {
            for (int to : g[i])
            {
                if (col[to])
                {

                    dc.addEdge(i, to, 1);
                }
            }
        }
    }

    dc.Maxflow(s, t);

    for (int i = 1; i <= n + 2; i++)
    {
        for (int j = dc.head[i]; j; j = dc.e[j].nxt)
        {
            //if (dc.e[j].w == 0)

            if (dc.e[j].w == 0)
                continue;

            tarjan::addEdge(i, dc.e[j].to);
        }
    }
    tarjan::solve(n + 2);
    vector<pii> ans;

    for (int i = 1; i <= n; i++)
    {
        for (int j = dc.head[i]; j; j = dc.e[j].nxt)
        {
            if (dc.e[j].w == 0)
            {
                int to = dc.e[j].to;

                if (tarjan::be[i] != tarjan::be[to] && (j % 2 == 0))
                {
                    if (i != s && to != t && to != s && i != t)
                        ans.push_back({min(i, to), max(i, to)});
                }
            }
        }
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());

    for (pii now : ans)
    {
        printf("%d %d\n", now.first, now.second);
    }
}