哪里有问题?
查看原帖
哪里有问题?
152652
AndyChen2005121楼主2020/11/28 21:22
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int in[100005], out[100005];
int dp[100005];
vector<int> g[100005];
void dfs(int x){
	if(out[x]==0) return;
	for(int i = 0; i < g[x].size(); i++){
		dp[g[x][i]]+=dp[x];
		dfs(g[x][i]);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		in[y]++;
		out[x]++;
		g[x].push_back(y);
	}
	for(int i = 1; i <= n; i++){
		if(in[i]==0){
			dp[i]=1;
			dfs(i);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(out[i]==0){
			ans+=dp[i];
		}
	}
	cout << ans << endl;
}
2020/11/28 21:22
加载中...