2 条题解

  • 0
    @ 2025-10-8 16:58:04
    #include <bits/stdc++.h>
    using namespace std;
    const int N=100010;
    int ans,dp[N];
    vector<int> G[N];
    void dfs(int x){
    	if(dp[x]) return ;//已经访问过,无需再次搜索
    	for(int y : G[x]){//遍历儿子
    		dfs(y);
    		dp[x] = max(dp[x], dp[y] + 1);//在儿子的边数中求最大
    	}
    	ans = max(ans, dp[x]);
    }
    signed main(){
    	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    	int n, m; cin >> n >> m;
    	for(int i, x, y; i <= m; i++) cin >> x >> y, G[x].push_back(y); //建边
    	memset(dp, 0, sizeof(dp));//初始化dp数组
    	ans = 0;
    	for(int i = 1; i <= n; i++) dfs(i); //搜索
    	cout << ans;
    	return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:54
      #include<bits/stdc++.h>
      using namespace std;
      const int N=100010;
      int ans,dp[N];
      vector<int>G[N];
      void dfs(int x){
      	if(dp[x]) return ;//已经访问过,无需再次搜索
      	for(int y:G[x]){//遍历儿子
      		dfs(y);
      		dp[x]=max(dp[x],dp[y]+1);//在儿子的边数中求最大
      	}
      	ans=max(ans,dp[x]);
      }
      signed main(){
      	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      	int n,m;cin>>n>>m;
      	for(int i,x,y;i<=m;i++)cin>>x>>y,G[x].push_back(y);//建边
      	memset(dp,0,sizeof(dp));//初始化dp数组
      	ans=0;
      	for(int i=1;i<=n;i++) dfs(i);//搜索
      	cout<<ans;
      	return 0;
      }
      • 1

      信息

      ID
      1582
      时间
      2000ms
      内存
      1024MiB
      难度
      6
      标签
      递交数
      55
      已通过
      19
      上传者