首页 > 代码库 > POJ 1904 King's Quest(强连通)
POJ 1904 King's Quest(强连通)
POJ 1904 King‘s Quest
题目链接
题意:n个男人,每个人都有一个喜欢的女人列表,现在给一个完美匹配,问所有完美匹配中,每个人可能娶到的女人列表
思路:强连通,建图,男的连一条边指向女,然后完美匹配的边女的指向男,然后求强连通,在同一个强连通分支并且是自己想娶的的就可能娶到
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <stack> using namespace std; const int N = 4005; int n; vector<int> g[N]; int ans[N], an; stack<int> S; int pre[N], dfn[N], dfs_clock, sccno[N], sccn; void dfs_scc(int u) { pre[u] = dfn[u] = ++dfs_clock; S.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { dfs_scc(v); dfn[u] = min(dfn[u], dfn[v]); } else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]); } if (pre[u] == dfn[u]) { sccn++; while (1) { int x = S.top(); S.pop(); sccno[x] = sccn; if (x == u) break; } } } void find_scc() { dfs_clock = sccn = 0; memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); for (int i = 1; i <= 2 * n; i++) if (!pre[i]) dfs_scc(i); } int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= 2 * n; i++) g[i].clear(); int a, b; for (int i = 1; i <= n; i++) { scanf("%d", &a); while (a--) { scanf("%d", &b); g[i].push_back(b + n); } } for (int i = 1; i <= n; i++) { scanf("%d", &a); g[a + n].push_back(i); } find_scc(); for (int i = 1; i <= n; i++) { an = 0; for (int j = 0; j < g[i].size(); j++) { if (sccno[i] == sccno[g[i][j]]) ans[an++] = g[i][j] - n; } sort(ans, ans + an); printf("%d", an); for (int j = 0; j < an; j++) printf(" %d", ans[j]); printf("\n"); } } return 0; }
POJ 1904 King's Quest(强连通)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。