Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n;
  6. vector<int> graph [101];
  7. bool used[101];
  8. int len[101];
  9.  
  10. void bfs(int v){
  11.     len[v]=1;
  12.     used[v]=true;
  13.     queue<int>q;
  14.     q.push(v);
  15.     while(!q.empty()){
  16.         v=q.front();
  17.         q.pop();
  18.         for (int i=0; i<graph[v].size();++i){
  19.             int to=graph[v][i];
  20.             if (!used[to]){
  21.                 used[to]=true;
  22.                 len[to]=(len[v]+1)%2;
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     cout.tie(nullptr);
  33.     cin >> n;
  34.     for (int i=1; i<=n; ++i){
  35.         int a;
  36.         while (cin >> a && a!=0){
  37.             graph[i].push_back(a);
  38.         }
  39.     }
  40.     bool ok=true;
  41.     for (int i =1; i<=n; ++i){
  42.         if (graph[i].empty()){
  43.             ok=false;
  44.         }
  45.     }
  46.     if (ok) {
  47.         vector<int>ans;
  48.         int cnt=0;
  49.         for (int i = 1; i <= n; ++i) {
  50.             if (!used[i]) {
  51.                 bfs(i);
  52.             }
  53.         }
  54.         for (int i=1; i<=n; ++i){
  55.             if (len[i]==0){
  56.                 cnt++;
  57.                 ans.push_back(i);
  58.             }
  59.         }
  60.         cout << cnt << '\n';
  61.         for (auto elem: ans){
  62.             cout << elem << " ";
  63.         }
  64.     }
  65.     else{
  66.         cout << 0;
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement