poj1741，poj 1904

題意：國王有n個兒子，現在有n個美女，每個兒子都有若干個夢中情人，現在已經有一個方案使每個王子都能與自己的夢中情人之一結婚。現在要求的是，對于每個兒子能選擇的配偶是誰（最終每個兒子都能結成婚）？

分析：這個題的建圖方法很特別。為了充分利用條件，即最后給出的那個完美匹配，將每個王子向他的夢中情人作一條有向邊，完美匹配方案中，美女向匹配的王子作一條有向邊。求出圖中的強連通分量，與王子在同一個強連通分量且該王子喜歡的美女就是答案。

正確性：王子集合{x1,x2,......,xn}，美女集合{y1,y2,......,yn}，假設在原完美匹配方案中每個匹配都是(xi,yi)，顯然yi是xi的一個選項。假如xi選了yj(j!=i)，則原先與yj匹配的王子xj要找另一個女人，yi要與另一個王子匹配，假如xj喜歡yi，那么yj就可以是xi的另一個選項了，假如xj不喜歡yi，那么就繼續下去拆散現有的完美匹配，直到有個王子喜歡yi。所以這樣就相當于要找一條由xi出發到yi的通路（等價于由xi出發回到xi的回路），只要這樣的回路存在，王子就可以與回路中任意一個他喜歡的美女匹配了。這樣也就相當于求包含xi的強連通分量。（注意：求出強連通分量之后，只有王子喜歡的美女才能匹配）。

#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> s;
vector<int> arc[5005],group[5005];
bool visited[5005],instack[5005],matrix[2001][2001];
int counter,low[5005],num[5005],sn,set[5005],n;
void tarjan(int u)
{
    int i,v;
    num[u]=low[u]=++counter;
    visited[u]=true;
    instack[u]=true;
    s.push(u);
    for(i=0;i<arc[u].size();i++)
    {
        v=arc[u][i];
        if(!visited[v])
        {
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }
        else if(instack[v])
            low[u]=min(low[u],num[v]);
    }
    if(num[u]==low[u])
    {
        do
        {
            v=s.top();
            if(v>n)//v is a girl
                group[sn].push_back(v);
            else
                set[v]=sn;
            instack[v]=false;
            s.pop();
        }while(u!=v);
        sort(group[sn].begin(),group[sn].end());
        sn++;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                matrix[i][j]=false;
        }
        for(int i=1;i<=n;i++)
        {
            int m;
            scanf("%d",&m);
            for(int j=0;j<m;j++)
            {
                int v;
                scanf("%d",&v);
                matrix[i][v]=true;
                arc[i].push_back(v+n);
            }
        }
        for(int i=1;i<=n;i++)
        {
            int u;
            scanf("%d",&u);
            arc[u+n].push_back(i);
        }
        for(int i=1;i<=2*n;i++)
            instack[i]=visited[i]=false;
        sn=counter=0;
        for(int i=1;i<=n;i++)
        {
            if(!visited[i])
                tarjan(i);
        }
        for(int i=1;i<=n;i++)
        {
            vector<int> ans;
            for(int j=0;j<group[set[i]].size();j++)
            {
                if(matrix[i][group[set[i]][j]-n])
                    ans.push_back(group[set[i]][j]-n);
            }
            printf("%d",ans.size());
            for(int j=0;j<ans.size();j++)
                printf(" %d",ans[j]);
            printf("\n");
            ans.clear();
        }
        for(int i=1;i<=2*n;i++)
            arc[i].clear();
        for(int i=0;i<sn;i++)
            group[i].clear();
    }
    return 0;
}

?