2 条题解

  • 0
    @ 2025-7-5 11:46:29
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N=1000+5;
    
    int n,ans;
    int a[N];
    
    int find(int where) {
    	for (int i=1; i<=n; i++)
    		if (a[i]==where&&i!=where) find(i),ans++;
    }
    
    int main() {
    //	freopen("relay.in","r",stdin);
    //	freopen("relay.out","w",stdout);
    
    	cin>>n;
    	for (int i=1; i<=n; i++) cin>>a[i];
    
    	for (int i=1; i<=n; i++)
    		if (!a[i]) {
    			ans++;
    			find(i);
    		}
    
    	cout<<ans;
    
    	return 0;
    }
    
    • 0
      @ 2023-3-25 17:20:55

      找出所有强联通分量缩点,然后从缩点往外拓展,所有能到达的点打上标记,答案为没有打上标记的点数。

      时间复杂度 O(n)\mathcal{O}(n)

      我菜,我写挂了()

      • 1

      信息

      ID
      393
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      (无)
      递交数
      74
      已通过
      48
      上传者