34392023-02-27 19:29:07k_balintKét csoportcpp14Time limit exceeded 86/100211ms44384 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 main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        while(1){
            cin>>k;
            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 << endl;
    for(int i=1;i<=n;i++){
        if(col[i]) cout << i << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
base86/100
1Accepted0/08ms15984 KiB
2Accepted0/059ms24188 KiB
3Accepted3/38ms16516 KiB
4Accepted3/38ms16724 KiB
5Accepted3/38ms17056 KiB
6Accepted3/38ms17264 KiB
7Accepted3/38ms17480 KiB
8Accepted2/28ms17576 KiB
9Accepted3/38ms17572 KiB
10Accepted3/38ms18008 KiB
11Accepted3/38ms17804 KiB
12Accepted3/314ms18576 KiB
13Accepted3/314ms18748 KiB
14Accepted3/314ms18880 KiB
15Accepted6/659ms25876 KiB
16Accepted7/765ms26288 KiB
17Accepted7/772ms26296 KiB
18Accepted6/6114ms33624 KiB
19Accepted6/6123ms34696 KiB
20Accepted6/6137ms34944 KiB
21Accepted6/6168ms42064 KiB
22Accepted7/7187ms44384 KiB
23Time limit exceeded0/7211ms44300 KiB
24Time limit exceeded0/7211ms44300 KiB