fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool odw[500002];
  4. vector<bool> wyn;
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(0);
  8.     cin.tie(0);
  9.     int n,m;cin>>n>>m;
  10.     vector<vector<int>> vec;
  11.     for(int i=0;i<n;i++)
  12.     {
  13.         vector<int> a;
  14.         vec.push_back(a);
  15.     }
  16.     wyn.resize(n);
  17.     for(int i=0;i<m;i++)
  18.     {
  19.         int a,b;cin>>a>>b;
  20.         vec[a-1].push_back(b-1);
  21.         vec[b-1].push_back(a-1);
  22.     }
  23.     queue<pair<int,int>> que;
  24.     for(int i=0;i<n;i++)
  25.     {
  26.         if(odw[i]==1)
  27.             continue;
  28.         else
  29.         {
  30.             que.push({i,1});
  31.             //cout<<i<<' '<<vec[i].size()<<endl;
  32.             if(vec[i].size()==0)
  33.                 {
  34.                     cout<<"NIE";
  35.                     return 0;
  36.                 }
  37.             while(!que.empty())
  38.             {
  39.                 pair<int,bool> a=que.front();
  40.                 que.pop();
  41.                 odw[a.first]=1;
  42.                 wyn[a.first]=a.second;
  43.                 for(auto x:vec[a.first])
  44.                 {
  45.                     if(odw[x]==0)
  46.                     {
  47.                         pair<int,bool> par={x,(a.second-1)*(-1)};
  48.                         que.push(par);
  49.                     }
  50.                 }
  51.             }
  52.  
  53.         }
  54.     }
  55.     cout<<"TAK";
  56.     for(auto x:wyn)
  57.     {
  58.         if(x)
  59.         {
  60.             cout<<endl<<'K';
  61.         }
  62.         else
  63.             cout<<endl<<'S';
  64.     }
  65. }
  66.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
3 3
2 1
2 3
1 3
stdout 
TAK
K
S
K
https://ideone.com/Bye0r9
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!