C++(g++ 7.5.0) 解法, 执行用时: 55ms, 内存消耗: 424K, 提交时间: 2022-09-20 20:11:49

#include<bits/stdc++.h>
using namespace std;
int fa[501],n,m,l;
int can[501];
int find(int x)
{
    if (fa[x] == x) return x;
    return find(fa[x]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>l;
        can[l]=1;
    }
    for(int i=1;i<=n;i++)
    {
        int a,k;
        cin>>a;
        int aa=find(i),bb;
        while(a--)
        {
            cin>>k;
            bb=find(k);
            if(aa!=bb)
                fa[k]=i;
        }
    }
    int flag=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            if(!can[i])
            {
                flag=1;
                break;
            }
            ans++;
        }
    }
    if(flag==0)
    cout<<ans<<endl;
    else
    cout<<-1<<endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 64ms, 内存消耗: 2348K, 提交时间: 2020-05-23 11:33:36

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>

using namespace std;

const int N = 1000;

int n,m;
vector<int> v[N];
int num[N];
int ans;
int rul[N];
int vis[N];

void dfs(int x,int y)
{
	vis[x] = 1;
	for(int i=0; i<v[x].size(); i++)
	{
		int a = v[x][i];
		if(!vis[a]) dfs(a,y);
		else if(a != y && rul[a]) 
		{
			rul[a] = 1;
			ans--;
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=0; i<m; i++) cin>>num[i];
	for(int i=1; i<=n; i++)
	{
		int a;
		cin>>a;
		for(int j=0; j<a; j++)
		{
			int b;
			cin>>b;
			v[i].push_back(b);
		}
	}
	for(int i=0; i<m; i++)
	{
		int a = num[i];
		if(!vis[a]) 
		{
			rul[a] = 1;
			ans++;
			dfs(a,a);
		}
	}
	for(int i=1; i<=n; i++) 
		if(!vis[i]) 
		{
			puts("-1");
			return 0;
		}
	cout<<ans;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 1292K, 提交时间: 2020-03-26 23:30:37

#include<bits/stdc++.h>
#define ri register int
#define maxn 510
using namespace std;
int a[maxn],n,m,k,l,r,ans;
bool can[maxn];
int find(int n)
{
	if(n==a[n])
	return n;
	else
	return find(a[n]);
}
int main()
{
	ans=0;
	scanf("%d%d",&n,&m);
	for(ri i=1;i<=n;i++)
	{
		can[i]=false;
		a[i]=i;
	}
	for(ri i=1;i<=m;i++)
	{
		scanf("%d",&k);
		can[k]=true;
	}
	for(ri i=1;i<=n;i++)
	{
		scanf("%d",&l);
		int xl=find(i),xr;
		while(l--)
		{
			scanf("%d",&r);
			xr=find(r);
			if(xl!=xr)
			a[r]=i;
		}
	}
	bool f=false;
	for(int i=1;i<=n;i++)
	if(a[i]==i)
	{
		if(!can[i])
		{
			f=true;
			break;
		}
		ans++;
	}
	if(f==false)
	printf("%d\n",ans);
	else
	printf("-1\n");
	return 0;
}