3440 2023. 02. 27 19:33:08 k_balint Két csoport cpp14 Elfogadva 100/100 128ms 44188 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=3e5+5;

int n;
vector<int> adj[c];
int col[c];
bool rossz[c];
vector<int> q;
bool vis[c];

void dfs(int v, int p){
    vis[v]=1; col[v]=p;
    for(int x:adj[v]){
        if(!vis[v]) dfs(x,p^1);
    }
}

int r(){
    int res=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+ch-'0';
        ch=getchar();
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    n=r();
    for(int i=1;i<=n;i++){
        int k;
        while(1){
            k=r();
            if(!k) break;
            adj[i].push_back(k);
        }
    }

    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs(i,0);
    }

    for(int i=1;i<=n;i++){
        int db=0;
        for(int x:adj[i]){
            if(col[i]==col[x]) ++db;
        }
        if(db>=2) q.push_back(i);
    }

    while(!q.empty()){
        int cur=q.back();
        q.pop_back();

        int db=0;
        for(int x:adj[cur]){
            if(col[cur]==col[x]) ++db;
        }

        if(db<2) continue;

        col[cur]^=1;
        for(int x:adj[cur]){
            int db=0;
            for(int y:adj[x]){
                if(col[x]==col[y]) ++db;
            }
            if(db>=2) q.push_back(x);
        }
    }

    int db=0;
    for(int i=1;i<=n;i++){
        if(col[i]) db++;
    }

    cout << db << '\n';
    for(int i=1;i<=n;i++){
        if(col[i]) cout << i << ' ';
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 8ms 15984 KiB
2 Elfogadva 0/0 35ms 24188 KiB
3 Elfogadva 3/3 8ms 16612 KiB
4 Elfogadva 3/3 8ms 16568 KiB
5 Elfogadva 3/3 8ms 16696 KiB
6 Elfogadva 3/3 8ms 17024 KiB
7 Elfogadva 3/3 8ms 17096 KiB
8 Elfogadva 2/2 8ms 17244 KiB
9 Elfogadva 3/3 8ms 17488 KiB
10 Elfogadva 3/3 8ms 17460 KiB
11 Elfogadva 3/3 8ms 17412 KiB
12 Elfogadva 3/3 10ms 18420 KiB
13 Elfogadva 3/3 10ms 18548 KiB
14 Elfogadva 3/3 10ms 18680 KiB
15 Elfogadva 6/6 37ms 25628 KiB
16 Elfogadva 7/7 41ms 26304 KiB
17 Elfogadva 7/7 46ms 26264 KiB
18 Elfogadva 6/6 70ms 33856 KiB
19 Elfogadva 6/6 75ms 34836 KiB
20 Elfogadva 6/6 86ms 34784 KiB
21 Elfogadva 6/6 96ms 41972 KiB
22 Elfogadva 7/7 108ms 44188 KiB
23 Elfogadva 7/7 128ms 43948 KiB
24 Elfogadva 7/7 128ms 43952 KiB