涛哥讲过这种题有木有...还出了丘比特的烦恼有木有...结果我还是没过有木有T T
首先对于一个完备匹配的图来说，不存在非匹配的点，因此将匹配边指向Y集，非匹配边指向X集，那么，在同一个强联通分量中的边势必是可以互相替换的。
但这道题就坑在他不是一个完备匹配，有非匹配的点，那么只求强联通分量是不够的，我最后半个小时才发现这个问题，结果也没时间打补丁，而且我们想的打补丁的方法也很丑，bfs两遍看未匹配点能走到哪些点，X集中的点还要逆向bfs...后来听ly讲了个十分精妙的补丁，新建两个点s和t，X集中的点如果未被匹配，则s->i，否则i->s，Y集中的点如果未被匹配，则t->i，否则i->t，这样就继续套用前面的算法，就可以解决这个bug了...380ms,目前最快的程序...其实这个加点的方法和bfs应该是异曲同工，不过确实是优美很多...
HK还是不会写，还是直接上板子...
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
const int maxn=200000,maxm=500000;
using namespace std;
int cx[maxn],cy[maxn],mk[maxn],q[maxn],src[maxn],pre[maxn];
int head[maxn],vtx[maxm],next[maxm],tot,n,m,P;
int tail[200000],nex[500000],sora[500000],ss,h,w_time;
int rel[500000],low[500000],st[500000],f[500000],v[500000];
int l[500000],r[500000];
char str[1005];
int Number[1005];
inline void Add(int a,int b)
{
vtx[tot]=b;
next[tot]=head[a];
head[a]=tot++;
}
inline int Maxmatch()
{
// memset(mk,-1,sizeof(mk));
for (int i=0;i<=n+m;i++) mk[i]=-1,cx[i]=-1,cy[i]=-1;
// memset(cx,-1,sizeof(cx));
// memset(cy,-1,sizeof(cy));
// for (int i=0;i<n;i++) cout<<cx[i]<<endl;
for (int p=1,fl=1,h,tail;fl;++p) {
fl=0;
h=tail=0;
for (int i=0;i<n;++i)
if (cx[i]==-1)
q[++tail]=i,pre[i]=-1,src[i]=i;
for (h=1;h<=tail;++h) {
int u=q[h];
if (cx[src[u]]!=-1) continue;
for (int pp=head[u],v=vtx[pp];pp;pp=next[pp],v=vtx[pp])
if (mk[v]!=p) {
mk[v]=p;
q[++tail]=cy[v];
if (cy[v]>=0) {
pre[cy[v]]=u;
src[cy[v]]=src[u];
continue;
}
int d,e,t;
for (--tail,fl=1,d=u,e=v;d!=-1;t=cx[d],cx[d]=e,cy[e]=d,e=t,d=pre[d]) ;
break;
}
}
}
int res=0;
for (int i=0;i<n;i++)
res+=(cx[i]!=-1);
return res;
}
void dfs(int x)
{
++w_time;
st[++h]=x;
rel[x]=w_time,low[x]=w_time,v[x]=1;
// cout<<x<<endl;
for (int i=x,ne;nex[i];) {
i=nex[i],ne=sora[i];
if (!v[ne]) dfs(ne);
if (v[ne]<=1) low[x]=min(low[x],low[ne]);
// cout<<x<<' '<<ne<<endl;
}
// cout<<low[x]<<' '<<rel[x]<<endl;
if (low[x]==rel[x]) {
for (;st[h]!=x;h--) f[st[h]]=x,v[st[h]]=2;
h--,f[x]=x,v[x]=2;
}
}
void origin()
{
ss=n+m+5;
for (int i=1;i<=ss;i++) tail[i]=i,nex[i]=0;
for (int i=1;i<=n+m+2;i++) {
v[i]=0,rel[i]=0,low[i]=0;
}
}
/*struct Graph{
int bs,now[maxn],next[maxm],go[maxm];
void add(int x,int y){
bs++;
go[bs]=y;
next[bs]=now[x];
now[x]=bs;
}
void clear(int n){
bs=0;
for(int i=1;i<=n;i++)now[i]=0;
}
}G,G1;*/
void link(int x,int y)
{
++ss,nex[tail[x]]=ss,tail[x]=ss,sora[ss]=y,nex[ss]=0;
// G.add(x,y);
// G1.add(y,x);
// ++ss,nex[tail[y]]=ss,tail[y]=ss,sora[ss]=x,nex[ss]=0;
// cout<<x<<' '<<y<<endl;
}
/*int ZZZ[maxm],DL[maxn],Hash[maxn];
inline void bfs(Graph G,int fl)
{
int h,t;
h=t=0;
for (int i=1;i<=n+m;i++){
if(fl&&cy[i-1]==-1){
DL[++t]=i;
Hash[i]=1;
}else if(!fl&&cx[i-1]==-1){
DL[++t]=i;
Hash[i]=1;
}else Hash[i]=0;
}
while(h<t){
h++;
for(int i=G.now[DL[h]];i;i=G.next[i]){
int j=G.go[i];
ZZZ[i]=1;
if(!Hash[j]){
Hash[j]=1;
DL[++t]=j;
}
}
}
}*/
int main()
{
freopen("i.in","r",stdin);
freopen("i.out","w",stdout);
for (char c = '0'; c <= '9'; c++)
Number[c] = c - 48;
for (char c = 'A'; c <= 'V'; c++)
Number[c] = c - 'A' + 10;
tot=2;
for (;scanf("%d%d%d",&n,&m,&P)==3;) {
for(int i=0;i<=n+m+2;i++){
head[i]=0;
}
tot=2;
for (int i=0;i<P;++i) {
int a=0,b=0;
scanf("%s", str + 1);
a = b = 0;
for (int j = 1; j <= 3; j++)
{
a = a * 32 + Number[str[j]];
b = b * 32 + Number[str[j + 3]];
}
Add(a,b);
// cout<<a<<' '<<b<<endl;
l[i]=a,r[i]=b;
}
// cout<<Maxmatch()<<endl;
Maxmatch();
// for (int i=0;i<n;i++) cout<<cx[i]<<endl;
origin();
// G.clear(n+m);
// G1.clear(n+m);
for (int i=0;i<P;i++) {
int a,b;
a=l[i],b=r[i];
// ZZZ[i+1]=0;
// cout<<a<<' '<<b<<endl;
if (cx[a]==b) link(a+1,b+1+n);
else link(b+1+n,a+1);
if (cy[b]!=-1)link(b+1+n,n+m+2);
else link(n+m+2,b+1+n);
if(cx[a]!=-1)link(n+m+1,a+1);
else link(a+1,n+m+1);
// cout<<endl;
}
for (int i=1;i<=n+m+2;i++) f[i]=i;
h=0,w_time=0;
for (int i=1;i<=n+m+2;i++)
if (!v[i]) dfs(i);
// for (int i=1;i<=n+m;i++) cout<<f[i]<<endl;
// bfs(G,1);
// bfs(G1,0);
int ans=0;
for (int i=0;i<P;i++) {
int a,b;
a=f[l[i]+1],b=f[r[i]+1+n];
if (a!=b && cx[l[i]]!=r[i] && cy[r[i]]!=l[i] && cx[l[i]]!=-1 && cy[r[i]]!=-1) ans++;
}
printf("%d\n",ans);
int fl=0;
for (int i=0;i<P;i++) {
int a,b;
a=f[l[i]+1],b=f[r[i]+1+n];
if (a!=b && cx[l[i]]!=r[i] && cy[r[i]]!=l[i] && cx[l[i]]!=-1 && cy[r[i]]!=-1) {
if(fl)printf(" ");
printf("%d",i);
fl=1;
}
}
printf("\n");
}
return 0;
}