UVA1327 King's Quest

King's Quest

题意

对于每个王子，寻找他喜欢并且可以娶的女孩，统计，按顺序输出。

思路

1. 可以考虑建图。在输入时，如果王子喜欢女孩，那么建一条从王子到女孩的边；

   如果女孩可以嫁给王子，建一条从女孩到王子的边。

2. 如果王子喜欢女孩，那么王子可以到达女孩；

   如果女孩可以嫁给王子，那么女孩就可以到达王子，

   于是想到 tarjan 寻找强连通分量。

3. 跑一遍 tarjan，找到图中的强连通分量。

4. 对于每个王子，遍历他可以到的点，

   如果那个点是女孩且王子与女孩在同一强连通分量内（即他们可以互相到达），

   存入女孩编号。

5. 对于女孩编号排序并输出。

模拟

样例：

4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4

• 为了避免与王子编号重复，第 \(x\) 个女孩的编号是 \(x+n\)。

细节

• 数组开大些。

• 多组数据，初始化。

• 输入输出很大，使用快读快输。

• 存女孩的数组可以重复使用，只需将指向下标的指针清 \(0\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int _ = 2000005;  
int n ,m ,ans[_];
int ts ,dfn[_] ,low[_] ,top ,stk[_]; //每个点的编号和栈
int scc_cnt ,all[_] ,id[_]; //记录强联通分量
int head[_] ,cnt;
struct Edge
{
    int to ,nxt;
}e[_ * 2]; //链式前向星

inline int read()
{
    int n = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
		n = (n << 1) + (n << 3) + (ch ^ 48), ch = getchar();
    return n * f;
} //引用的时候 “a=read();” 即可（a为任意一个整形变量）

inline void write(int x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
} //调用时“write(a)” 即可，a为任意一个整型变量  

inline void init()
{
    ts = 0 ,scc_cnt = 0 ,cnt = 0 ,top = 0;
    memset(head ,0 ,sizeof(head));
    memset(dfn ,0 ,sizeof(dfn));
    memset(low ,0 ,sizeof(low));
    memset(id ,0 ,sizeof(id));
    memset(stk ,0 ,sizeof(stk));
    memset(all ,0 ,sizeof(all));
}

inline void add(int from ,int to)
{
    e[++cnt] = {to ,head[from]};
    head[from] = cnt;
}

inline void tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int to = e[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[u] = min(low[u] ,low[to]);
        }
        else if(!id[to])
            low[u] = min(low[u] ,dfn[to]);
    } 
    if(dfn[u] == low[u])
    {
        id[u] = ++scc_cnt;
        ++all[scc_cnt];
        while(stk[top] != u)
        {
            id[stk[top--]] = scc_cnt;
            ++all[scc_cnt];
        }
        top--;
    }
}

int main()
{
    while(scanf("%d" ,&n) != EOF)
    {
        init(); //初始化
        //读入并建图 
        for(int i = 1;i <= n;++i)
        {
            int m;
            m = read(); 
            for(int j = 1;j <= m;++j)
            {
            	int x;
                x = read();
                add(i ,x + n);
            }
        }
        for(int i = 1;i <= n;++i)
        {
        	int x;
            x = read();
            add(x + n ,i);
        }
        //tarjan 
        for(int i = 1;i <= n;++i)
            if(!dfn[i]) tarjan(i);
        //对于每个王子，遍历他能到的点
        for(int i = 1;i <= n;++i)
        {
            int count = 0;
            for(int j = head[i];j;j = e[j].nxt)
            {
                int to = e[j].to;
                if(to > n && id[i] == id[to])
                //是女孩且在强连通分量当中 
                    ans[++count] = to - n;
            }
            sort(ans + 1,ans + count + 1);
            write(count) ,putchar(' ');
            for(int j = 1;j <= count;++j)
                write(ans[j]) ,putchar(' ');
            putchar('\n');
        }
    }
    return 0;
}