test/aoj/3198.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:27:26+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198

Depends on

• matching/bipartite.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../matching/bipartite.cpp"
#undef call_from_test

const int MAX = 5050;
int ex[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;

  Bipartite G(n+n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    ex[a][b]=1;
    G.add_edge(0+a,n+b);
  }

  int res=G.build();

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;

    if(ex[x][y])
      res-=G.cut_edge(0+x,n+y);
    else
      G.add_edge(0+x,n+y);

    ex[x][y]^=1;

    res+=G.build();
    cout<<(res==n?"Yes":"No")<<'\n';
  }
  return 0;
}

#line 1 "test/aoj/3198.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "matching/bipartite.cpp"

#line 3 "matching/bipartite.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(N M)
struct Bipartite{
  int time;
  vector< vector<int> > G;
  vector<int> match,used,dead;

  Bipartite(int n):
    time(0),G(n),match(n,-1),used(n,-1),dead(n,0){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  int dfs(int v){
    used[v]=time;
    for(int u:G[v]){
      if(dead[u]) continue;
      int w=match[u];
      if((w<0) or (used[w]<time and dfs(w))){
        match[v]=u;
        match[u]=v;
        return 1;
      }
    }
    return 0;
  }

  int build(){
    int res=0;
    for(int v=0;v<(int)G.size();v++){
      if(dead[v] or ~match[v]) continue;
      time++;
      res+=dfs(v);
    }
    return res;
  }

  int disable(int v){
    assert(!dead[v]);
    int u=match[v];
    if(~u) match[u]=-1;
    match[v]=-1;
    dead[v]=1;
    time++;
    return ~u?dfs(u)-1:0;
  }

  int enable(int v){
    assert(dead[v]);
    dead[v]=0;
    time++;
    return dfs(v);
  }

  int cut_edge(int u,int v){
    assert(find(G[u].begin(),G[u].end(),v)!=G[u].end());
    assert(find(G[v].begin(),G[v].end(),u)!=G[v].end());
    G[u].erase(find(G[u].begin(),G[u].end(),v));
    G[v].erase(find(G[v].begin(),G[v].end(),u));
    if(match[u]==v){
      match[u]=match[v]=-1;
      return 1;
    }
    return 0;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/3198.test.cpp"
#undef call_from_test

const int MAX = 5050;
int ex[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;

  Bipartite G(n+n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    ex[a][b]=1;
    G.add_edge(0+a,n+b);
  }

  int res=G.build();

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;

    if(ex[x][y])
      res-=G.cut_edge(0+x,n+y);
    else
      G.add_edge(0+x,n+y);

    ex[x][y]^=1;

    res+=G.build();
    cout<<(res==n?"Yes":"No")<<'\n';
  }
  return 0;
}

Back to top page