Cod sursa(job #701701)

Utilizator ilincaSorescu Ilinca ilinca Data 1 martie 2012 17:22:26
Problema Felinare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<cstdio>
#include<cstring>
#include<vector>

#define nmax 8196

using namespace std;

int n, m, sup = 0, A[nmax], B[nmax], s[2*nmax];
vector<int> g[2*nmax];
bool v[nmax];

void scan(){
  int i, a, b;
  scanf("%d%d", &n, &m);
  for(i = 1; i <= m; ++i){
    scanf("%d%d", &a, &b);
    g[a].push_back(b+n);
    g[b+n].push_back(a);
  }
}

bool pairup(int k){
  int i;
  v[k] = true;
  for(i = 0; i != g[k].size(); ++i)
    if(A[g[k][i]] == 0){
      A[g[k][i]] = k;
      B[k] = g[k][i];
      return true;
    }
  for(i = 0; i != g[k].size(); ++i)
    if(!v[g[k][i]] && pairup(A[g[k][i]])){
      A[g[k][i]] = k;
      B[k] = g[k][i];
      return true;
    }
  return false;
}

void cuplaj(){
  int ok, i;
  do{
    ok = false;
    for(i = 1; i <= n; ++i)
      if(v[i] == false && B[i] == 0)
        ok |= pairup(i);
    memset(v, 0, sizeof(v));
  } while(ok == true);
}

void suport(int k){
  int i;
  for(i = 0; i != g[k].size(); ++i){
    if(s[g[k][i]] == true)
      continue;
    s[g[k][i]] = true;
    s[A[g[k][i]]] = false;
    suport(A[g[k][i]]);
  }
}

void rez(){
  int i;
  for(i = 1; i <= n; ++i)
    if(B[i]){
      s[i] = true;
      ++sup;
    }
  for(i = 1; i <= n; ++i)
    if(s[i] == false)
       suport(i);
}

void print(){
  int i;
  printf("%d\n", n*2-sup);
  for(i = 1; i <= n; ++i){
    if(s[i] == 0 && s[i+n] == 0)
      printf("3\n");
    if(s[i] && s[i+n])
      printf("0\n");
    if(s[i] && s[i+n] == 0)
      printf("2\n");
    if(s[i] == 0 && s[i+n])
      printf("1\n");
  }
}

int main(){
  freopen("felinare.in", "r", stdin);
  freopen("felinare.out", "w", stdout);

  scan();

  cuplaj();

  rez();

  print();

  return 0;
}