158352025-03-04 00:17:47oKét csoportcpp17Elfogadva 100/100123ms21300 KiB
#include <bits/stdc++.h>
using namespace std;

int ru(){
  char c;
  do{
    c=getchar();
  }
  while(!isdigit(c));
  int x=0;
  do{
    x*=10;
    x+=c-'0';
    c=getchar();
  }
  while(isdigit(c));
  return x;
}

void wc(char c){
  putchar(c);
}

void wu(int x){
  int h=1,c=1;
  while(h<=x/10){
    h*=10;
    c++;
  }
  while(c--){
    int d=x/h;
    x-=d*h;
    x*=10;
    wc(d+'0');
  }
}

int main()
{
  int n=ru();
  if(n<1000){
    //return 1;
  }
  vector<vector<int>>g(n+1);
  for(int i=1;i<=n;i++){
    int a;
    while(a=ru()){
      g[i].push_back(a);
      //cout<<i<<' '<<a<<endl;
    }
  }
  vector<int>v(n+1),p(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;
        p[b]=a;
        q.push_back(b);
      }
    }
  }
  vector<int>ans(n+1,-1);
  for(int i=1;i<=n;i++){
    int c=0;
    for(int j:g[i]){
      if(v[j]==v[i]){
        c++;
      }
    }
    if(c!=2){
      ans[i]=v[i]%2;
    }
  }
  auto dfs=[&](auto f,int i)->void{
    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++){
    if(ans[i]==v[i]%2){
      continue;
    }
    int a=i;
    int b=i;
    while(a==b){
      b=p[a];
      for(int c:g[b]){
        if(c!=a&&ans[c]==ans[b]){
          ans[b]=v[a]%2;
          a=b;
          break;
        }
      }
    }
  }
  int m=count(ans.begin(),ans.end(),0);
  wu(m);
  wc('\n');
  for(int i=1;i<=n;i++){
    if(ans[i]==0){
      wu(i);
      wc(' ');
    }
  }
  wc('\n');
  return 0;
}

bool test(){
  int T=0;
  while(true){
      T++;
     int n=12;
    stringstream s;
    s<<n<<endl;
    vector<vector<int>>g(n+1);
    for(int i=1;i<=n;i++){
      for(int j=0;j<3;j++){
        int x=rand()%n+1;
        if(x==i){
          j--;
          continue;
        }
        if(g[i].size()==3||g[x].size()==3||count(g[i].begin(),g[i].end(),x))continue;
        g[i].push_back(x);
        g[x].push_back(i);
      }
    }
     for(int i=1;i<=n;i++){
      for(int j:g[i])s<<j<<' ';s<<"0\n";
    }
    //cout<<s.str()<<endl<<endl;
    if(false){
      bool wk=0;
      for(int b=0;b<(1<<n);b++){
          wk=1;
        for(int i=1;i<=n;i++){
        int c=0;
        for(int j:g[i]){
          if((b>>i-1&1)==(b>>j-1&1)){
            c++;
          }
        }
        if(c>=2){
          wk=0;
        }
      }
        if(wk){
        for(int i=1;i<=n;i++)cout<<i<<' '<<(b>>i-1&1)<<endl;
          break;
        }
      }
      cout<<endl<<endl;
      if(!wk)exit(10);
    }
    cin.rdbuf(s.rdbuf());
    stringstream u;
    auto oo=cout.rdbuf(u.rdbuf());
    int res=main();
    cout.rdbuf(oo);
    //cout<<u.str()<<endl;
    if(res){
      cout<<u.str()<<endl;
      cout<<"FAILED "<<T<<endl;
      exit(1);
    }
    else if(T%100==0)cout<<"OK "<<T<<endl;
  }
}

//bool _=test();
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/032ms7220 KiB
3Elfogadva3/31ms508 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms556 KiB
6Elfogadva3/31ms500 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva2/21ms316 KiB
9Elfogadva3/31ms316 KiB
10Elfogadva3/31ms328 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva3/34ms972 KiB
13Elfogadva3/34ms1076 KiB
14Elfogadva3/34ms980 KiB
15Elfogadva6/632ms7156 KiB
16Elfogadva7/735ms7220 KiB
17Elfogadva7/739ms7220 KiB
18Elfogadva6/674ms14300 KiB
19Elfogadva6/674ms14392 KiB
20Elfogadva6/681ms14272 KiB
21Elfogadva6/6114ms21236 KiB
22Elfogadva7/7120ms21300 KiB
23Elfogadva7/7123ms21264 KiB
24Elfogadva7/7123ms21300 KiB