二分図の判定(図の探索)
2314 ワード
#include
#include
using namespace std;
const int MAX_N=1e2+6;
vector<int>G[MAX_N];
int V,color[MAX_N];
bool dfs(int v,int c){
color[v]=c;
for(int i=0;iif(color[G[v][i]]==c)return false;
if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false;
}
return true;
}
void solve(){
for(int i=0;iif(color[i]==0)
if(!dfs(i,1)){
cout<<"No"<return ;
}
}
cout<<"Yes"<int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>V;
solve();
}