POJ 1904 强连通分量

POJ 1904

题意

给出一个匹配表.n个王子,接下来n行.行首代表王子喜欢$k$个公主,接下来是$k_i$个公主的编号.最后一行给出当前一种 : 与每个王子结婚的公主编号(喜欢才能结婚).所有王子都要结婚

求可以与每个王子结婚的所有公主编号(并且所有王子都要结婚)

思路

  1. 若王子u喜欢公主v,u->v建边
  2. 由最后一行的一种结婚情况来反向建边; 王子u与公主v结婚,v->u;

建图后

  1. 发现在同一强连通分量中.{王子1与公主2,王子2与公主1}也可以结婚 (满足喜欢和王子都要结婚).且强连通分量中恰好是偶数情况
  2. 所以和每个王子结婚的公主都在同一强连通分量中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 4e3+5;
const int M = 2e5 + N;

struct { int v,next; } edge[M];
int head[N],low[N],dfn[N],sta[N],belong[N],ans[N];
bool instack[N];
int g,cnt,top,scc;

int n;

void add(int u,int v) {
    edge[g].v = v;
    edge[g].next = head[u];
    head[u] = g++;
}

void init() {
    g = cnt = top = scc = 0;
    memset(   head,-1,sizeof    head);
    memset(    dfn, 0,sizeof     dfn);
    memset(instack, 0,sizeof instack);
}

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    sta[++top] = u;
    instack[u] = 1;
    for (int i=head[u]; i!=-1;i=edge[i].next) {
        int to = edge[i].v;
        if (!dfn[to]) {
            tarjan(to);
            low[u] = min(low[u],low[to]);
        } else if (instack[to])
            low[u] = min(low[u],dfn[to]);
    }
    if (low[u] == dfn[u]) { // 缩点
        scc++;
        int to;
        do {
            to = sta[top--];
            instack[to] = 0;
            belong[to] = scc;
        } while(u != to);
    }
}

void solve() {
    for (int u=1; u<=n; ++u) { //遍历每个王子
        int count = 0;
        for (int i=head[u]; i!=-1; i=edge[i].next) { //判断王子指向的妹纸是否在同一强连通中
            int to = edge[i].v;
            if (belong[u] == belong[to])
                ans[count++] = to-n; // 记录下妹子编号
        }
        sort(ans,ans+count);
        printf("%d",count);
        for (int i=0; i<count; ++i)
            printf(" %d",ans[i]);
        printf("\n");
    }
}

int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d",&n) != EOF) { //可持久化
        init();
        for (int i=1; i<=n; ++i) {
            int k; scanf("%d",&k);
            while (k--) {
                int v; scanf("%d",&v);
                add(i,v+n);
            }
        }
        for (int i=1; i<=n; ++i) {
            int v; scanf("%d",&v);
            add(v+n,i);
        }
        for (int i=1; i<=2*n; ++i) // 男女一共2n个点
            if (!dfn[i])
                tarjan(i);
        solve();
    }
    return 0;
}

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！