C++14(g++5.4) 解法, 执行用时: 49ms, 内存消耗: 760K, 提交时间: 2020-04-25 10:37:47

#include <iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define lowbit(x) (x) & -(x)
#define ll long long
const int INF = 0x3f3f3f3f;
int student[30010];
int a[30010];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        student[i] = i;
    }
}

int find1(int x) {
    int r = x;
    while (student[r] != r) r = student[r];
    int j = x;
    while (student[j] != r) {
        int i = j;
        j = student[j];
        student[i] = r;
    }
    return r;
}

void myset(int x, int y) {
    x = find1(x);
    y = find1(y);
    if (student[x] != student[y]);
    student[x] = y;
}

int main() {
    //freopen("data.in", "r", stdin);
    //freopen("practice.out", "w", stdout);
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    init(n);
    for (int i = 1; i <= m; i++) {
        int num,f;
        scanf("%d", &num);
        scanf("%d", &f);
        for (int j = 2; j <= num; j++) {
            int s;
            scanf("%d", &s);
            myset(f, s);
        }
    }
    int check = find1(q);
    int j = 0;
    for (int i = 1; i <= n; i++) {
        if (find1(i) == check)
            a[j++] = i;
    }
    printf("%d\n", j);
    int flag = 0;
    for (int i = 0; i < j; i++) {
        if (!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 112ms, 内存消耗: 2868K, 提交时间: 2020-05-07 11:25:26

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[3000000];
int f[3000000];
int fin(int x)
{
	if(f[x]==x)
	return x;
	else
	return f[x]=fin(f[x]);
}
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int t;
		cin>>t;
		int x=0,y=0;
		int p;
		for(int j=1;j<=t;j++)
		{
			cin>>p;
			if(x==0)
			x=p;
			else
			{
				if(y==0)
				{
					y=p;
				}
				else
				{
					x=y;
					y=p;
				}
				f[fin(x)]=fin(y);
			}
		}
	}
	int ans=0;
	vector<int>u;
	for(int i=1;i<=n;i++)
	{
		if(fin(i)==fin(k))
		{
			ans++;
			u.push_back(i);
		}
	}
	cout<<ans<<endl;
	for(int i:u)
	cout<<i<<" ";
}