Happy Path

Sample Input 1 

1
3 2
1 2
3 2

Sample Output 1

2

解析：其实我们只需要求得每个节点的“儿子”有多少个，然后把它们相加即可，结果是：0+1+2+0+4+3=10；

例如：

以下过程按代码进行模拟：

son [ 6 ] = 0;                               dp[ 6 ] = 0;                                                                                 son [ 6 ]=1;//叶节点设为0

son [ 5 ] += son [ 6 ] =1;             dp[ 5 ] += dp [ 6 ] =0;          dp[ 5 ] += son [ 5 ] =0+1=1;            son [ 5 ]++;

son [ 2 ] += son [ 5 ] =2;             dp[ 2 ] += dp [ 5 ] =1;          dp[ 2 ] += son [ 2] =1+2=3;             son [ 2 ]++;

son [ 4 ] = 0;                                                                                                                                  son [ 4 ] =1;//叶节点设为0

son [ 1 ] += son [ 2 ] =3;             dp[ 1 ] +=dp[ 2 ] =3;                                                                                   

              += son [ 4 ] =4;             dp[ 1 ] +=dp[ 4 ]=3;              dp[ 1 ] += son [ 1 ] =3+4=7;           son [ 1 ]++;

son [ 3 ] += son [ 2 ] =2;              dp[ 3 ]+=son[ 2 ]=3;

相加的过程是通过dp[ ] 实现的,ans只需要找到入度为0的点，把该点的 dp[ ] 值加上即可;

ans += dp [ 1 ] =7;

ans += dp [ 3 ] =7+3=10;

即结果为：10；

详细看代码；

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include<iostream>
using namespace std;
const int MAXN = 100010;
const int mod = 1e9 + 7;
vector<int> G[MAXN];
int vis[MAXN], in[MAXN];
int son[MAXN], dp[MAXN];
long long ans;

void dfs(int x) {
	if(!G[x].size()) {//如果执行这一步，说明x为叶节点 
		son[x] = 1;
		return ;
	}
	for(int i = 0; i < G[x].size(); ++i) {
		int u = G[x][i];
		if(vis[u]) {
			son[x] += son[u];
			son[x] %= mod;
			continue;
		}
		vis[u] = 1;
		dfs(u);
		dp[x] += dp[u];//路径数 
		son[x] += son[u];
		dp[x] %= mod, son[x] %= mod;
	}
	
	dp[x] += son[x];
	son[x]++;//把自己加上 
	dp[x] %= mod, son[x] %= mod;
}

int main() {
	int n, m, T;
	scanf("%d", &T);
	while(T--) {
		for(int i = 0; i < MAXN; ++i) G[i].clear(), son[i] = 0;
		for(int i = 0; i < MAXN; ++i) vis[i] = in[i] = dp[i] = 0;
		scanf("%d %d", &n, &m);
		for(int i = 0; i < m; ++i) {
			int a, b;
			scanf("%d %d", &a, &b);
			in[b]++;
			G[a].push_back(b);
		}
		for(int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());//从小到大排序 
            G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
        }//删除重边,题目要求点不一样,留一条边即可 
		ans = 0;
		for(int i = 1; i <= n; ++i) {
			if(in[i]) continue;//找入度为0的点，入度不是0，则continue 
			dfs(i);
			ans += dp[i];
			ans %= mod;
		}
		printf("%lld\n", ans);
	}
	return 0;
}