[题目链接]
[算法]
不难发现，本题是要我们求出二分图最大匹配的不可行边，我们可以将此问题转化为求可行边的补集
那么，怎样求二分图的可行边？ 我们可以先来考虑一个简化的情况 ： 二分图的最大匹配为完备匹配
我们求出任意一组二分图最大匹配，将匹配边(x,y)看作y到x的有向边，将非匹配(y,x)看作x到y的有向边，若x到y有增广路，则在新图G'中x到y存在路径
此时，若边(x,y)为可行边，则 ：(x,y)当前为匹配边，或当前x匹配u，y匹配v，我们让x匹配y，u和v失去匹配，但我们可以找到一条从u到v的增广路
仔细观察，我们发现(x,y)为可行边等价于在新图G'上x和y在同一个强连通分量中
在本题中，并没有保证最大匹配为完备匹配，但我们可以借助网络流的源点和汇点，不妨先运行dinic算法，然后，判定条件就变成了 ： 在残余网络上，
若x和y在同一个强连通分量内，则(x,y)为可行边
时间复杂度 : O(T * Sqrt(N + M)) （ 其中，Sqrt表示开方 )
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXT 200010
const int inf = 2e9; struct edge
{
int to,w,id,nxt;
} e[MAXT << ]; int i,p,n,m,t,S,T,timer,tot,cnt,scc,q,w,id,top;
int head[MAXN << ],u[MAXT],v[MAXT],depth[MAXN << ],s[MAXN << ],
belong[MAXN << ],ans[MAXT],low[MAXN << ],dfn[MAXN << ];
bool flag[MAXT],instack[MAXN << ]; inline void addedge(int u,int v,int id)
{
tot++;
e[tot] = (edge){v,,id,head[u]};
head[u] = tot;
tot++;
e[tot] = (edge){u,,id,head[v]};
head[v] = tot;
}
inline bool bfs()
{
int i,l,r,u,v,w;
static int q[MAXN << ];
memset(depth,,sizeof(depth));
q[l = r = ] = S;
depth[S] = ;
while (l <= r)
{
u = q[l];
l++;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!depth[v] && w)
{
depth[v] = depth[u] + ;
q[++r] = v;
if (v == T) return true;
}
}
}
return false;
}
inline int dinic(int u,int flow)
{
int i,v,w,rest = flow,k;
if (u == T) return flow;
for (i = head[u]; i && rest; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (depth[v] == depth[u] + && w)
{
k = dinic(v,min(rest,w));
if (!k) depth[v] = ;
e[i].w -= k;
e[i ^ ].w += k;
rest -= k;
}
}
return flow - rest;
}
inline void tarjan(int u)
{
int i,v,w;
low[u] = dfn[u] = ++timer;
instack[u] = true;
s[++top] = u;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!w) continue;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
} else if (instack[v]) low[u] = min(low[u],dfn[v]);
}
if (dfn[u] == low[u])
{
scc++;
do
{
v = s[top];
top--;
belong[v] = scc;
instack[v] = false;
} while (v != u);
}
}
int main()
{ scanf("%d%d%d",&n,&m,&t);
for (i = ; i <= t; i++) scanf("%d%d",&u[i],&v[i]);
tot = ;
S = n + m + ;
T = n + m + ;
for (i = ; i <= n; i++) addedge(S,i,);
for (i = ; i <= t; i++) addedge(u[i],v[i] + n,i);
for (i = ; i <= m; i++) addedge(n + i,T,);
while (bfs())
{
while (dinic(S,inf));
}
memset(flag,true,sizeof(flag));
for (p = ; p <= n; p++)
{
for (i = head[p]; i; i = e[i].nxt)
{
q = e[i].to;
w = e[i].w;
id = e[i].id;
if (q > n && q <= n + m && !w)
flag[id] = false;
}
}
for (i = ; i <= n + m + ; i++)
{
if (!dfn[i])
tarjan(i);
}
for (i = ; i <= t; i++)
{
if (belong[u[i]] == belong[v[i] + n])
flag[i] = false;
}
for (i = ; i <= t; i++)
{
if (flag[i])
ans[++cnt] = i;
}
printf("%d\n",cnt);
for (i = ; i <= cnt; i++) printf("%d ",ans[i]);
printf("\n"); return ; }