dfs搜索代码求调
  • 板块P3914 染色计数
  • 楼主CD43
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/26 15:59
  • 上次更新2025/7/26 21:46:10
查看原帖
dfs搜索代码求调
755114
CD43楼主2025/7/26 15:59
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,m;
bitset<10001>c[10001];
int a[10001][10001];
vector<int>b[10001];
bool t[10001];
int num[10001];
int dfs(int x,int cc)
{
	if(t[x])return 1;
	t[x]=1;
    bool q=1;
	int ans=num[x];
	if(c[x][cc])ans--;
	for(int i=0;i<b[x].size();i++)
	{
        if(q&&t[b[x][i]]==0)
        {
            q=0;
            ans=1;
        }
		for(int j=1;j<=num[x];j++)
		{
			if(cc==a[x][j])continue;
			ans*=dfs(b[x][i],a[x][j]);
			ans%=mod;
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		for(int j=1;j<=x;j++)
		{
			cin>>a[i][j];
			c[i][j]=1;
		}
		num[i]=x;
	}
	
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		b[x].push_back(y);
		b[y].push_back(x);
	}
	
	int ans=dfs(1,0);
	cout<<ans%mod;
	return 0;
}
2025/7/26 15:59
加载中...