萌新第一天学c艹20分求助
查看原帖
萌新第一天学c艹20分求助
660871
2011Andy楼主2023/7/21 14:50
#include <bits/stdc++.h>
#define int long long
using namespace std;
//拓扑排序:DAG:有向无环图 
//处理入口点信息和出口点信息
const int N = 100005;
int ind[N] , oud[N];
int dp[N];
int n , m;
vector<int > v[N]; 
signed main(){ 
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i++){
		int a , b;
		cin >> a >> b;
		v[a].push_back(b);
		ind[b]++;
		oud[a]++;
	}
	//建立对列:将所有入度为零的点入队
	queue<int > q;
	for(int i = 1 ; i <= n ; i++){
		if(!ind[i]){
			q.push(i);
			dp[i] = 1;
		}
	}
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int i = 0 ; i < v[t].size() ; i++){
			int a = v[t][i];
			ind[a]--;
			dp[a] = (dp[a] + dp[t]);
			if(!ind[a]) q.push(a);
		}
	}
	int maxn = 0;
	for(int i = 1 ; i <= n ; i++){
		if(!oud[i]) maxn = (maxn + dp[i]);
	}
	cout << maxn;
	return 0;
}
2023/7/21 14:50
加载中...