CF-1675D. Vertical Paths

题意:每次可以选择一条路径，要求这条路径中每个点都是上一个点的子节点，求最少需要几条路径将所有点走完

思路:将每个点有没有子节点判断出来，因为只有没有子节点的点需要新增一条路，所以需要路径的最小数目就是没有子节点的节点个数，从每个根节点出发，深搜一遍即可。

注意：可以开临时vector来节约时间。

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int N=2e5+50;

ll pre[N],vis[N];

vector<ll> q;

signed main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll t;cin>>t;

  while(t--){

    ll n;cin>>n;

    ll ans=n;

    vector<ll> sum(n+1,0);

    for(ll i=1;i<=n;i++){

         cin>>pre[i];vis[i]=0;

         if(!sum[pre[i]]) ans--;

         sum[pre[i]]++;

    }

    if(n==1){cout<<"1"<<endl<<"1"<<endl<<"1"<<endl<<endl;continue;}

    cout<<ans<<endl;

    for(ll i=1;i<=n;i++){

      if(!sum[i]){

        ll p=i;

        while(!vis[p]){

          vis[p]=1;

          q.push_back(p);p=pre[p];

        }

        cout<<q.size()<<endl;

        for(ll j=q.size()-1;j>=0;j--){

          cout<<q[j];

          if(j!=0) cout<<" ";

          else cout<<endl;

        }

        q.clear();

      }

    }

    cout<<endl;

  }

}

巴特西

CF-1675D. Vertical Paths

最新文章

热门文章