2 条题解

  • 1
    @ 2023-3-25 17:20:55

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

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

    我菜,我写挂了()

    • -1
      @ 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;
      }
      
      • 1

      信息

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