本文主要是介绍POJ 1904 King's Quest 强连通分量+二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
好题啊，先赞一个，这里有个讲的好的，感觉让我讲也没他这么好。。。 King's Quest#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 2010;
vector <int> G[maxn*2];
vector <int> G2[maxn*2];
int pre[maxn*2];
int low[maxn*2];
int sccno[maxn*2];
int dfs_clock;
int scc_cnt;
stack <int> S;
int n, m;
int cnt[maxn*2], mp[maxn*2];
void dfs(int u)
{pre[u] = low[u] = ++dfs_clock;S.push(u);for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!pre[v]){dfs(v);low[u] = min(low[u], low[v]);}else if(!sccno[v])low[u] = min(low[u], pre[v]);}if(pre[u] == low[u]){scc_cnt++;while(1){int x = S.top();S.pop();sccno[x] = scc_cnt;if(x == u)break;}}
}
void find_scc()
{dfs_clock = scc_cnt = 0;memset(sccno, 0, sizeof(sccno));memset(pre, 0, sizeof(pre));for(int i = 1; i <= 2*n; i++)if(!pre[i])dfs(i);
}
int a[maxn][maxn];
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){int p;scanf("%d", &p);while(p--){int v;scanf("%d", &v);G[i].push_back(v+n);a[i][v] = 1;}}for(int i = 1; i <= n; i++){int x;scanf("%d", &x);G[x+n].push_back(i);}find_scc();for(int i = n+1; i <= 2*n; i++)G2[sccno[i]].push_back(i);for(int i = 1; i <= scc_cnt; i++)sort(G2[i].begin(), G2[i].end());for(int i = 1; i <= n; i++){int x = sccno[i];//printf("%d", G2[x].size());int b[maxn], num = 0;for(int j = 0; j < G2[x].size(); j++){int v = G2[x][j];if(v > n && a[i][v-n])b[num++] = v-n;}printf("%d", num);for(int j = 0; j < num; j++)printf(" %d", b[j]);printf("\n");}return 0;
}这篇关于POJ 1904 King's Quest 强连通分量+二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
