#P1774. 第5题-小美吃饭
-
1000ms
Tried: 33
Accepted: 8
Difficulty: 8
所属公司 :
美团
时间 :2024年3月30日
-
算法标签>强连通分量
第5题-小美吃饭
题目思路
本题难度较大，需要前置知识强连通分量。
考虑一个人u暗恋另外一个人v，则我们让v连一条有向边到u，表示u属于v的子节点，此时可以构成一个有向图。
然而有可能出现三角恋的情况，即成环，对于成环的情况，在环上只要请了任意一个人来，那环上其它所有点都必须来，所以这种情况我们可以将其缩点为一个人。
缩点需要采用强连通分量的tarjan算法，可以将环缩成一个点。
但是题目已经说明一个人最多暗恋一个人，所以缩点后的有向图的每个点的入度最多为1，相当于一个节点只有最多只有一个父节点，那么入度为0的点作为根结点，就可以形成很多的树。
对所有的树进行dp，设f[u]为第u的其子树有多少种情况。
假设第u个人来了，那么其子节点v（也就是暗恋他的人）可来可不来，当第u个人不来，那么子树都不能来，这个其实只有一种情况，所以f[u] = f[u] * (f[v] + 1)
最终将所有的根结点的答案相乘，这里会出现所有人都不来的情况，需要除去这一种情况。
时间复杂度O(n)
代码
Python
n, m = map(int, input().split(' '))
g = [[] for _ in range(n)]
mod = 10**9 + 7
for _ in range(m):
u, v = map(int, input().split(' '))
u, v = u - 1, v - 1
g[v].append(u)
low, dfn, stk, in_stk, id = [0] * n, [0] * \
n, [0] * n, [False] * n, [0] * n
global timestamp, scc_cnt
timestamp, scc_cnt = 0, 0
def tarjan(u):
global timestamp, scc_cnt
timestamp += 1
low[u] = dfn[u] = timestamp
stk.append(u)
in_stk[u] = True
for v in g[u]:
if dfn[v] == 0:
tarjan(v)
low[u] = min(low[u], low[v])
elif in_stk[v]:
low[u] = min(low[u], dfn[v])
if low[u] == dfn[u]:
while True:
y = stk.pop()
id[y] = scc_cnt
in_stk[y] = False
if y == u:
break
scc_cnt += 1
for i in range(n):
if dfn[i] == 0:
tarjan(i)
vg = [[] for _ in range(scc_cnt)]
d, f = [0] * scc_cnt, [1] * scc_cnt
for u in range(n):
for v in g[u]:
if id[u] != id[v]:
vg[id[u]].append(id[v])
d[id[v]] += 1
def dfs(u):
for v in vg[u]:
dfs(v)
f[u] = f[u] * (f[v] + 1) % mod
ans = 1
for i in range(scc_cnt):
if d[i] == 0:
dfs(i)
ans = ans * (f[i] + 1) % mod
print((ans + mod - 1) % mod)
import java.util.*;
public class Main {
static final int MOD = 1000000007;
static int timestamp = 0, sccCnt = 0;
static List<Integer>[] g;
static int[] low, dfn, stk, id, d, f;
static boolean[] inStk;
static List<Integer>[] vg;
static int n, m;
static int top = -1;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
g = new ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int u = scanner.nextInt() - 1;
int v = scanner.nextInt() - 1;
g[v].add(u);
}
low = new int[n];
dfn = new int[n];
stk = new int[n];
inStk = new boolean[n];
id = new int[n];
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
tarjan(i);
}
}
vg = new ArrayList[sccCnt];
d = new int[sccCnt];
f = new int[sccCnt];
Arrays.fill(f, 1);
for (int i = 0; i < sccCnt; i++) {
vg[i] = new ArrayList<>();
}
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (id[u] != id[v]) {
vg[id[u]].add(id[v]);
d[id[v]]++;
}
}
}
long ans = 1;
for (int i = 0; i < sccCnt; i++) {
if (d[i] == 0) {
dfs(i);
ans = ans * (f[i] + 1) % MOD;
}
}
System.out.println((ans + MOD - 1) % MOD);
scanner.close();
}
static void tarjan(int u) {
low[u] = dfn[u] = ++timestamp;
stk[++top] = u;
inStk[u] = true;
for (int v : g[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (inStk[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
while (true) {
int y = stk[top--];
id[y] = sccCnt;
inStk[y] = false;
if (y == u) break;
}
sccCnt++;
}
}
static void dfs(int u) {
for (int v : vg[u]) {
dfs(v);
f[u] = (int)((long)f[u] * (f[v] + 1) % MOD);
}
}
}
题目描述
小美有n个朋友，她准备请其中一些朋友来吃饭。 其中有一些朋友有暗恋关系：假设a暗恋b，那么小美带上b的时候a也必须去，否则a就会不开心。 小美想知道，一共有多少种不同的请客方案可以让每个人都开心？由于答案可能过大，请对109+7取模。
输入描述
第一行输入两个正整数n,m，代表小美的朋友数量、暗恋的关系数量。 接下来的m行，每行输入两个正整数u,v，代表第u个人暗恋第v个人。 1≤n,m≤105 1≤u,v≤n 保证每个人最多只会暗恋一个人。
输出描述
一个整数，代表小美的请客方案数。
样例1
输入
2 1
1 2
输出
2
说明
两个方案：只请 1 号，或者同时请 1 号和 2 号。
请注意，不能只请 2 号，否则 1 号会不开心。
样例2
输入
3 3
1 2
2 3
3 1
输出
1
说明
显然 3 个人必须全部请客，否则总有人会不开心。