526互联

Codeforces Round 787 (Div. 3)D. Vertical Paths

发布时间 2023-12-14 14:56:17作者: cxy8

题目链接
题意：给定一棵树，将这棵树划分成几天互不相交的链，要求最小化链的数量
思路：每个叶子节点一定在一条链中，所以链的数量就是叶子节点的数量，从叶子节点往上跳直到根节点，边跳边标记，路径上所有点都属于这条链。
坑：

  1. 数据大时，不要轻易使用memset不然会t到起飞
  2. vector不要开太多就比如不要vector<int>a[N]这样也会t
#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f

using namespace std;
const int N = 2e5+10;
int t; 
int d[N], p[N], vis[N], n;
void solve()
{
	cin >> n;
	rep(i,1,n)
	{
		int x; cin >> x;
		p[i] = x;
		d[x]++;
	}
	if(n==1)
	{
	    cout << 1 << endl << 1 << endl << 1 << endl;
	    cout << endl;
	    return;
	}
	int ans = 0;
	vector<int>a[n];
	rep(i,1,n)
		if(!d[i])
		{
			int k = i;
			while(!vis[k] && k != p[k])
			{
				a[ans].push_back(k);
				vis[k] = 1;
				k = p[k];
			}	
			if(k == p[k] && !vis[k])
			{
				a[ans].push_back(k);
				vis[k] = 1;
			}		
			ans++;
		}
	rep(i,1,n)	d[i] = 0, vis[i] = 0;
	cout << ans << endl;
	rep(i,0,ans-1)
	{
		cout << a[i].size() << endl;
		fep(i,a[i].size()-1,0)	cout << x << ' ';
		cout << endl;
	}
	cout << endl;
}

int main()
{
	IOS	
  	freopen("1.in", "r", stdin);
	cin >> t;
	while(t --)	
	solve();
	return 0;
}