前置芝士： 最大流 & 二分圖匹配

原題鏈接：P10940 舞動的夜晚

本題題意：給出一張二分圖，求該圖最大匹配的必不經邊

定理1：對于原二分圖中任意邊\((x,y)\)，若\((x,y)\)為匹配邊，并且在殘量網絡中分屬不同強連通分量,則\((x,y)\)為必經邊。

定理2：對于原二分圖中任意邊\((x,y)\)，若\((x,y)\)為匹配邊或\((x,y)\)在殘量網絡中屬于同一強連通分量，則\((x,y)\)為可行邊。

推論：
對于原二分圖中任意邊\((x,y)\)，若\((x,y)\)為非匹配邊且在殘量網絡中分屬不同強連通分量，則\((x,y)\)為必不經邊。

對于上述定理，我們進行簡單證明：

對于定理1，若\((x,y)\)屬于同一強連通分量，那么我們必然可以找到一條由非匹配邊構成的由\(x\)到\(y\)路徑，若我們將路徑中由左部點到右部點的邊替換原匹配中的匹配邊，顯然仍然是最大匹配，這與其為必經邊矛盾，故原定理得證。

對于定理2，用類似方法同樣可以證明，這里不再贅述。

顯然，必不經邊的集合是可行邊在原二分圖邊集中的補集所以上面我們提出的推論正確。

那么本題做法就顯而易見了，求出任意最大匹配，對求出最大匹配后的殘量網絡求連通分量，對于每一條原二分圖上的邊根據上述推論判斷即可。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10,M=4e5+10,inf=LONG_LONG_MAX;
int h[N],to[M],nx[M],vl[M],idx;
int now[N],d[N];
int dfn[N],low[N],fa[M];
bool in[N];
int sc[N],scc;
int res[M],cnt;
int tn,st[N],top;
int n,m,s,t,T;
queue<int> q;

bool bfs()
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();
    d[s]=1,now[s]=h[s];
    q.push(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];~i;i=nx[i])
        {
            int v=to[i];
            if(d[v] || !vl[i]) continue;
            d[v]=d[u]+1;
            now[v]=h[v];
            q.push(v);
            if(v==t) return 1;
        }
    }
    return 0;
}

int dinic(int u,int flow)
{
    if(u==t) return flow;
    int res=flow,k=0;
    for(int i=now[u];~i && flow;i=nx[i])
    {
        int v=to[i];
        now[u]=i;
        if(d[v]==d[u]+1 && vl[i])
        {
            k=dinic(v,min(res,vl[i]));
            if(!k) d[v]=0;
            vl[i]-=k;
            vl[i^1]+=k;
            res-=k;
        }
    }
    return flow-res;
}

void add(int u,int v,int w)
{
    nx[idx]=h[u];
    to[idx]=v;
    vl[idx]=w;
    h[u]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++tn;
    st[++top]=u;
    in[u]=1;
    for(int i=h[u];~i;i=nx[i])
    {
        if(!vl[i]) continue;
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v]) low[u]=min(low[u],dfn[v]);
    }

    if(dfn[u]==low[u])
    {
        scc++;
        int x;
        do
        {
            x=st[top--];
            in[x]=0;
            sc[x]=scc;
        } while(x!=u);
    }
}

signed main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m>>T;
    for(int i=1;i<=T;i++)
    {
        int u,v;
        cin>>u>>v;
        v+=n;
        fa[idx]=u;
        add(u,v,1);
        fa[idx]=v;
        add(v,u,0);
    }

    s=0,t=n+m+1;
    for(int i=1;i<=n;i++) add(s,i,1),add(i,s,0);
    for(int i=1;i<=m;i++) add(i+n,t,1),add(t,i+n,0);

    int ans=0;
    while(bfs())
    {
        int flow=0;
        while(flow=dinic(s,inf)) ans+=flow;
    }

    for(int i=1;i<=n+m;i++) if(!dfn[i]) tarjan(i);
    for(int i=0;i<=idx;i++)
    {
        int u=fa[i],v=to[i];
        if(u==0 || v==n+m+1) break;
        if(i%2==1) continue;
        if(sc[u]!=sc[v] && vl[i]) res[++cnt]=ceil((i+1)/2.0);
    }//利用鏈式前向星成對變換性質找到原二分圖上的邊
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++) cout<<res[i]<<" ";
    cout<<'\n';
}