题目思路

本题难度较大，需要前置知识强连通分量。

考虑一个人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就会不开心。 小美想知道，一共有多少种不同的请客方案可以让每个人都开心？由于答案可能过大，请对$10^9+7$取模。

输入描述

第一行输入两个正整数$n,m$，代表小美的朋友数量、暗恋的关系数量。 接下来的m行，每行输入两个正整数$u,v$，代表第$u$个人暗恋第$v$个人。 $1\leq n,m \leq 10^5$ $1\leq u,v \leq n$ 保证每个人最多只会暗恋一个人。

输出描述

一个整数，代表小美的请客方案数。

样例1

输入

2 1
1 2

输出

2

说明

两个方案：只请 1 号，或者同时请 1 号和 2 号。
请注意，不能只请 2 号，否则 1 号会不开心。

样例2

输入

3 3
1 2
2 3
3 1

输出

1

说明

显然 3 个人必须全部请客，否则总有人会不开心。