[长沙网络赛 I] 二分图最大匹配 强连通分量

[Link]

给定一个二分图，问你哪些边永远不可能成为最大匹配的边。

比赛的时候全败在题上了……
这道题我见过三次，第一次在上一年训练的时候见到，随便YY一下全手写花了不到1小时就过了；第二次在多校见少考虑了一种情况WA全场；第三次，hopcroft karp模板右边不能匹配居然match2不是-1而是n，直接又WA全场，把-1改成n立马过了。我简直不能再蠢……
实际这题还是很简单的(多校那个解题报告的解法要加各种边还得匹配两次感觉很不科学……)
做法就是先匹配，然后匹配边先排除这是肯定的。
然后匹配边从右往左连，非匹配边从左往右连。做强连通。
最后如果一条边符合下面三种情况之一就是可以作为匹配边的。

1. 
   这个的意思是要连的边两个点在同一个强连通分量。具体换边的方法就是沿着到彼此的路径交替互换就行了。
2. 
   左边的点被左边一个未被匹配的空点可达，换边的方法就是从空点一直走过来，交替互换。
3. 
   右边的点可达一个右边未被匹配的空点，换边的方法就是沿着这条路径一直走到空点，然后交替互换。

所以思路就明确了，SCC以后判连通性即可。
本来模块不能外传……但是想到我们的模块已经落后别人10条街了，而且网络赛本来就公开了代码……

#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, int> PII;
typedef long long ll;
const int MAXN = 100005;
int n, m, e;
int match1[MAXN], match2[MAXN];
int Q[MAXN], D1[MAXN], D2[MAXN];
vector <int> E[MAXN];

inline bool bfs() {
    int s = 0, t = 0, u, v;
    memset(D1, -1, sizeof(D1));
    memset(D2, -1, sizeof(D2));
    for (int i = 0; i < n; i++)
        if (match1[i] == -1)
            Q[t++] = i, D1[i] = 0;
    while (s != t)
        if ((u = Q[s++]) != n)
            for (int i = 0; i < (int)E[u].size(); i++)
                if (D2[v = E[u][i]] == -1) {
                    D2[v] = D1[u] + 1;
                    if (D1[match2[v]] == -1)
                        D1[Q[t++] = match2[v]] = D2[v] + 1;
                }
    return D1[n] != -1;
}

bool dfs(int u) {
    for (int i = 0, v; i < (int)E[u].size(); i++)
        if (D2[v = E[u][i]] == D1[u] + 1 && (D2[v] = -1) && (match2[v] == n || dfs(match2[v]))) {
            match1[u] = v;
            match2[v] = u;
            D1[u] = -1;
            return true;
        }
    D1[u] = -1;
    return false;
}

inline int hopcroft_karp() {
    memset(match1, -1, sizeof(match1));
    for (int i = 0; i < m; i++)
        match2[i] = n;
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0, u; j < (int)E[i].size(); j++)
            if (match2[u = E[i][j]] == n) {
                match1[i] = u;
                match2[u] = i;
                ret++;
                break;
            }
    while (bfs())
        for (int i = 0; i < n; i++)
            if (match1[i] == -1 && dfs(i))
                ret++;
    return ret;
}

int toNum(char c) {
	if (c >= '0' && c <= '9') return c - '0';
	return c - 'A' + 10;
}

int trans(char *s) {
	return toNum(s[0]) * 32 * 32 + toNum(s[1]) * 32 + toNum(s[2]);
}

struct SCC_T {
	int n;
	int dfn[MAXN], low[MAXN], id[MAXN], num, st[MAXN], top, in[MAXN], tot; 
	vector <int> E[MAXN];
	int come[MAXN], go[MAXN];

	void clear(int _n) {
		n = _n;
		rep (i, n) E[i].clear();
		memset(dfn, 0, sizeof(int) * n); 
		memset(low, 0, sizeof(int) * n); 
		memset(in, 0, sizeof(int) * n); 
		memset(id, 0xff, sizeof(int) * n); 
		memset(come, 0, sizeof(int) * n);
		memset(go, 0, sizeof(int) * n);
	}

	void addedge(int x, int y) {
		E[x].push_back(y);
	}
 
	void tarjan(int now){ 
		in[st[top++] = now] = true; 
		dfn[now] = low[now] = ++tot;
		int i; 
		for (int ii = E[now].size() - 1; ii >= 0; --ii){ 
			i = E[now][ii]; 
			if (!dfn[i]){ 
				tarjan(i); 
				low[now] = min(low[now], low[i]);
			}
			else if (in[i]) 
				low[now] = min(low[now], dfn[i]); 
		}
		if (dfn[now] == low[now]){
			do{
				i = st[--top];
				in[i] = false;
				id[i] = num;
			}while (i != now);
			++num;
		}
	}
	void gao() { 
		for (int i = top = num = tot = 0; i < n; ++i) 
			if (!dfn[i]) 
				tarjan(i); 
	}

	void bfs(int (&vis)[MAXN], const vector <int> (&E)[MAXN]) {
		static int Q[MAXN];
		int qh = 0, qt = 0;
		rep (i, n)
			if (vis[i])
				Q[qt++] = i;
		while (qh < qt) {
			int u = Q[qh++];
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (!vis[v]) {
					vis[v] = 1;
					Q[qt++] = v;
				}
			}
		}
	}

	void calc() {
		bfs(come, E);
		static vector <int> E2[MAXN];
		rep (i, n) E2[i].clear();
		rep (i, n) rep (j, E[i].size()) E2[E[i][j]].push_back(i);
		bfs(go, E2);
	}
}SCC;

int main() {
	while (scanf("%d%d%d", &n, &m, &e) != EOF) {
		static map <int, int> id[MAXN];
		rep (i, n) E[i].clear(), id[i].clear();
		rep (i, e) {
			char s[10];
			scanf("%s", s);
			int u = trans(s);
			int v = trans(s + 3);
			E[u].push_back(v);
			assert(!id[u].count(v));
			id[u][v] = i;
		}
		hopcroft_karp();
		SCC.clear(n + m);
		rep (u, n) {
			if (match1[u] != -1) SCC.addedge(match1[u] + n, u);
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (v != match1[u]) SCC.addedge(u, v + n);
			}
		}
		SCC.gao();
		rep (i, m)
			if (match2[i] == n)
				SCC.go[n + i] = 1;
		rep (i, n)
			if (match1[i] == -1)
				SCC.come[i] = 1;
		SCC.calc();
		vector <int> ans;
		rep (u, n) rep (i, E[u].size()) {
			int v = E[u][i];
			if (SCC.come[u] || SCC.go[v + n] || SCC.id[u] == SCC.id[v + n] || match1[u] == v) continue;
			ans.push_back(id[u][v]);
		}
		sort(ans.begin(), ans.end());
		printf("%d\n", (int)ans.size());
		rep (i, ans.size()) {
			if (i) putchar(' ');
			printf("%d", ans[i]);
		}
		puts("");
	}
}