POJ 1904 King's Quest 【强连通分量】

题目链接：http://poj.org/problem?id=1904

题意：
有n个王子喜欢n个姑娘，一个王子可以喜欢多个姑娘，王子只能娶一个姑娘，现在问每个王子能选哪几个姑娘，使得其它王子都能娶到喜欢的姑娘（保证有解）
题解：
强连通分量，用Tarjan比较简单。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int size = 4005;
const int size2 = 1000005;
const int size3 = 2005;

struct edges {
int y, next;
} ed[size2];

int head[size], stack[size], instack[size], dfn[size], low[size];
int map[size3][size3], sccno[size];
vector<int> ans;

int n, m, cnt = 0, qcnt = 0, top = 0, scccnt = 0;

void add(int x, int y) {
    ed[cnt].y = y;
    ed[cnt].next = head[x];
    head[x] = cnt ++;
}

void Tarjan(int rt) {
    dfn[rt] = low[rt] = ++qcnt;
stack[++top] = rt;
    instack[rt] = 1;

int temp;
for ( int i = head[rt]; i != -1; i = ed[i].next ) {
        temp = ed[i].y;
if(!dfn[temp]) {
            Tarjan(temp);
            low[rt] = min(low[rt], low[temp]);
        } else if(instack[temp]) low[rt] = min(low[rt], low[temp]);
    }

int temp2;
if(dfn[rt] == low[rt]) {
        scccnt ++;
do {
            temp2 = stack[top --];
            instack[temp2] = 0;
            sccno[temp2] = scccnt;
        } while( temp2 != rt );
    }
}

void init() {
memset(stack, 0, sizeof(stack));
memset(instack, 0, sizeof(instack));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(sccno, 0, sizeof(sccno));
    top = qcnt = scccnt = 0;
}

int main() {
// freopen("1904.in", "r", stdin);
memset(map, 0, sizeof(map));
memset(head, -1, sizeof(head));
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ ) {
scanf("%d", &m);
for ( int j = 1; j <= m; j ++ ) {
int x;
scanf("%d", &x);
            add(i, x+n);
map[i][x] = 1;
        }
    }

for ( int i = 1; i <= n; i ++ ) {
int x;
scanf("%d", &x);
        add(x+n, i);
    }

    init();

for ( int i = 1; i <= n; i ++ ) {
if(!dfn[i]) Tarjan(i);
    }

for ( int i = 1; i <= n; i ++ ) {
        ans.clear();
for ( int j = n+1; j <= n*2; j ++ ) {
if(map[i][j-n] && sccno[i] == sccno[j]) {
                ans.push_back(j-n);
            }
        }
printf("%d ", ans.size());
for ( int j = 0; j < ans.size(); j ++ ) {
printf("%d ", ans[j]);
        }
puts("");
    }

return 0;
}