158222025-03-03 21:45:32oKét csoportcpp17Runtime error 42/100206ms25140 KiB
#include <bits/stdc++.h>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin>>n;
  vector<vector<int>>g(n+1);
  for(int i=1;i<=n;i++){
    int a;
    while(cin>>a,a){
      g[i].push_back(a);
      //cerr<<i<<' '<<a<<endl;
    }
  }
  vector<int>v(n+1);
  for(int i=1;i<=n;i++){
    if(v[i]){
      continue;
    }
    v[i]=1;
    deque<int>q;
    q.push_back(i);
    while(!q.empty()){
      int a=q.front();
      q.pop_front();
      for(int b:g[a]){
        if(v[b]){
          continue;
        }
        v[b]=v[a]+1;
        q.push_back(b);
      }
    }
  }
  vector<int>ans(n+1,-1);
  auto dfs=[&](auto f,int i)->void{
    for(int j:g[i]){
      if(v[j]==v[i]+1){
        ans[i]=v[i]%2;
      }
    }
    if(ans[i]<0){
      return;
    }
    for(int j:g[i]){
      if(v[j]!=v[i]){
        continue;
      }
      if(ans[j]>=0){
        continue;
      }
      ans[j]=ans[i]^1;
      f(f,j);
    }
  };
  for(int i=1;i<=n;i++){
    dfs(dfs,i);
  }
  for(int i=1;i<=n;i++){
    if(ans[i]>=0){
      continue;
    }
    ans[i]=v[i]%2;
    dfs(dfs,i);
  }
  for(int i=1;i<=n;i++){
    int c=0;
    for(int j:g[i]){
      if(ans[j]==ans[i]){
        c++;
      }
    }
    if(c>1){
      return 2;
    }
  }
  cout<<count(ans.begin(),ans.end(),0)<<endl;
  for(int i=1;i<=n;i++){
    if(ans[i]==0){
      cout<<i<<' ';
    }
  }
  cout<<endl;
  return 0;
}
SubtaskSumTestVerdictTimeMemory
base42/100
1Accepted0/01ms500 KiB
2Accepted0/057ms8244 KiB
3Accepted3/31ms316 KiB
4Accepted3/31ms316 KiB
5Accepted3/31ms316 KiB
6Accepted3/31ms316 KiB
7Accepted3/31ms316 KiB
8Runtime error0/21ms500 KiB
9Accepted3/31ms316 KiB
10Accepted3/31ms316 KiB
11Runtime error0/31ms316 KiB
12Accepted3/36ms1092 KiB
13Runtime error0/36ms1084 KiB
14Runtime error0/37ms1212 KiB
15Accepted6/657ms8388 KiB
16Runtime error0/759ms8240 KiB
17Runtime error0/764ms8480 KiB
18Accepted6/6118ms16532 KiB
19Runtime error0/6122ms16308 KiB
20Runtime error0/6135ms16656 KiB
21Accepted6/6180ms24812 KiB
22Runtime error0/7188ms24372 KiB
23Time limit exceeded0/7206ms25140 KiB
24Runtime error0/7195ms24944 KiB