#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)
java
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);
}
}
}
C++
#include <iostream>
#include <vector>
#include <algorithm>
#define fi first
#define se second
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5+10;
int cl[N]; // 用于标记环上结点的颜色
int ks[N]; // 选定环上的一个结点作为环缩点后的结点
vector<pair<int,int> > edges;
vector<int> g[N]; // 图
// 并查集
int p[N];
int find(int u) {
if(u != p[u]) p[u] = find(p[u]);
return p[u];
}
// 树上DP,u为当前结点,f为到达u的上一个结点
int dfs(int u, int f) {
long long temp = 1;
for(int i = 0;i < g[u].size();++ i ) {
int v = g[u][i];
if(v == f) continue;
temp = temp * dfs(v, u) % mod; // 子树情形的累乘
}
return (temp + 1) % mod;
}
int main() {
int n, m; cin>>n>>m;
// 初始化
for(int i = 1;i <= n;i++){
ks[i] = 1e9;
p[i] = i;
}
int fa[N]; // 每个结点的上一个结点
int color = 1; // 环上颜色
for(int i = 1;i <= m;++ i ){
int a, b; cin>>a>>b;
edges.push_back(make_pair(a, b));
fa[a] = b;
int tempa = a, tempb = b;
a = find(a), b = find(b); // 父结点
if(a != b) p[a] = b;
/*
两个点已经在一个集合里面了,那么这条边相当于是在环上的一条边,
使用fa数组进行回溯,基环上的结点如果有多个指针,也一定是指向
环外的,所以环上结点的上一个结点一定也在环上,本题的性质决定的。
*/
else {
int now = tempa;
ks[color] = min(ks[color], now); // 环上父结点选择最小的
cl[now] = color; // 为环上结点创建标记
now = fa[now];
while(now != tempa){
// if(now == 0) break;
ks[color] = min(ks[color], now);
cl[now] = color;
now = fa[now];
}
color++;
}
}
// 建立图
for(int i = 0;i < m;++ i ) {
int a = edges[i].first, b = edges[i].second;
if(cl[a] > 0 && cl[b] == 0) g[ks[cl[a]]].push_back(b);
else if(cl[b] > 0 && cl[a] == 0) g[ks[cl[b]]].push_back(a);
else if(cl[a] == 0 && cl[b] == 0) g[b].push_back(a);
}
// 树上DP
long long ans = 1;
for(int i = 1;i <= n;++ i ) {
if(cl[i] > 0 && ks[cl[i]] == i) ans = 1ll * ans * dfs(i, 0) % mod; // 总根节点
else if(cl[i] == 0 && p[i] == i) ans = 1ll * ans * dfs(i, 0) % mod; // 总根节点
}
cout << (ans - 1 + mod) % mod << endl;
}
题目描述
小美有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 个人必须全部请客,否则总有人会不开心。