99932024-03-23 18:18:38111Két csoportcpp17Runtime error 33/100231ms61648 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
#ifndef ONLINE_JUDGE
	freopen("be2.txt","r",stdin);
#endif
	int N;
	cin>>N;
	vector<vector<int>>g(N+1);
	for(int i=1;i<=N;i++){
		for(int j;cin>>j,j;){
			g[i].push_back(j);
		}
	}
	vector<int>v(N+1);
	auto dfs1=[&](auto self,int i)->void{
		for(int j:g[i]){
			if(v[j]){
				continue;
			}
			v[j]=v[i]^3;
			self(self,j);
		}
	};
	vector<int>a(N+1);
	auto dfs2=[&](auto self,int i)->void{
		vector<pair<int,int>>w;
		for(int j:g[i]){
			if(a[j]){
				continue;
			}
			int c=0;
			for(int k:g[j]){
				if(v[k]!=v[j]){
					c++;
				}
			}
			w.emplace_back(c,j);
		}
		sort(w.begin(),w.end(),greater<>());
		for(auto[c,j]:w){
			if(a[j]){
				continue;
			}
			a[j]=a[i]^3;
			self(self,j);
		}
	};
	for(int i=1;i<=N;i++){
		if(v[i]){
			continue;
		}
		v[i]=1;
		a[i]=1;
		dfs1(dfs1,i);
		dfs2(dfs2,i);
	}
	for(int i=1;i<=N;i++){
		int c=0;
		for(int j:g[i]){
			if(a[j]==a[i]){
				c++;
			}
		}
		if(c>1){
			exit(1);
		}
	}
	vector<int>ans;
	for(int i=1;i<=N;i++){
		if(a[i]==1){
			ans.push_back(i);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<i<<' ';
	}
	cout<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base33/100
1Accepted0/03ms1864 KiB
2Accepted0/065ms18456 KiB
3Accepted3/33ms2228 KiB
4Accepted3/33ms2440 KiB
5Accepted3/33ms2524 KiB
6Accepted3/33ms2528 KiB
7Accepted3/33ms2556 KiB
8Runtime error0/23ms2648 KiB
9Accepted3/33ms3064 KiB
10Runtime error0/33ms3108 KiB
11Runtime error0/33ms3308 KiB
12Accepted3/38ms4844 KiB
13Runtime error0/38ms4864 KiB
14Runtime error0/39ms5540 KiB
15Accepted6/665ms20000 KiB
16Runtime error0/765ms19520 KiB
17Runtime error0/775ms23020 KiB
18Accepted6/6133ms36220 KiB
19Runtime error0/6134ms35080 KiB
20Runtime error0/6156ms49096 KiB
21Time limit exceeded0/6201ms53576 KiB
22Time limit exceeded0/7202ms50344 KiB
23Time limit exceeded0/7230ms57848 KiB
24Time limit exceeded0/7231ms61648 KiB