POJ 1904 King's Quest（强连通图）题解

题意：n个王子有自己喜欢的ki个公主，有n个公主，每个王子只能娶一个自己喜欢的公主且不能绿别的王子。现在给你一种王子娶公主的方案，并且保证这种方案是正确的。请你给出，每个王子能娶哪些公主，要求娶这些公主时，其他王子也能娶到公主。

思路：还以为是完全匹配，直接暴力匹配显然TLE了。正解是缩点...我们把每个王子指向自己喜欢的公主们，然后把给定的方案中的公主指向自己嫁给的王子，然后缩点，同一个点中王子喜欢的公主都能娶。因为每个王子指向的肯定都是公主（至少两个），公主指向的肯定都是王子，所以想要形成一个强连通图这个图中王子公主数量肯定是相同的，那么假如王子选择一个自己喜欢的公主，那么这个图中的其他的王子可以选择其他的公主，显然肯定能完全匹配。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

int head[maxn], ans[maxn], tot;

struct Edge{

    int to, next;

}edge[maxn * maxn];

int low[maxn], dfn[maxn], Stack[maxn], belong[maxn];

int index, top, scc;

bool instack[maxn];

void addEdge(int u, int v){

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void tarjan(int u){

    int v;

    low[u] = dfn[u] = ++index;

    Stack[top++] = u;

    instack[u] = true;

    for(int i = head[u]; i != -; i = edge[i].next){

        v = edge[i].to;

        if(!dfn[v]){

            tarjan(v);

            if(low[u] > low[v]) low[u] = low[v];

        }

        else if(instack[v] && low[u] > dfn[v]){

            low[u] = dfn[v];

        }

    }

    if(low[u] == dfn[u]){

        scc++;

        do{

            v = Stack[--top];

            instack[v] = false;

            belong[v] = scc;

        }while(v != u);

    }

}

void solve(int n){

    memset(dfn, , sizeof(dfn));

    memset(instack, false, sizeof(instack));

    index = scc = top = ;

    for(int i = ; i <= n; i++){

        if(!dfn[i])

            tarjan(i);

    }

}

void init(){

    tot = ;

    memset(head, -, sizeof(head));

}

int main(){

    int n;

    while(~scanf("%d", &n)){

        int k, tmp;

        init();

        for(int i = ; i <= n; i++){

            scanf("%d", &k);

            while(k--){

                scanf("%d", &tmp);

                addEdge(i, tmp + n);

            }

        }

        for(int i = ; i <= n; i++){

            scanf("%d", &tmp);

            addEdge(tmp + n, i);

        }

        solve( * n);

        int ret;

        for(int u = ; u <= n; u++){

            ret = ;

            for(int i = head[u]; i != -; i = edge[i].next){

                int v = edge[i].to;

                if(belong[v] == belong[u]){

                    ans[ret++] = v - n;

                }

            }

            sort(ans, ans + ret);

            printf("%d", ret);

            for(int i = ; i < ret; i++){

                printf(" %d", ans[i]);

            }

            printf("\n");

        }

    }

    return ;

}