Untitled
unknown
plain_text
a year ago
1.3 kB
5
Indexable
Never
#include<bits/stdc++.h> #define DilligentArch() ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); #define testcase(t) int t; cin>>t; while(t--) #define pb push_back typedef long long ll; using namespace std; const int N = 1e5+10; vector<int>g[N]; int clr[N]; bool vis[N]; ll v,e; bool checkdfs(int vertex) { if(clr[vertex]==-1)clr[vertex]=1; //vis[vertex] = true; for(int child : g[vertex]) { //if(vis[child]) //continue; if(clr[child]==-1) { clr[child]=1-clr[vertex]; if(!checkdfs(child)) return false; } else if(clr[child]==clr[vertex]) return false; } return true; } bool checkbi() { memset(clr,-1,sizeof(clr)); for(ll i=0; i<v; i++) { if(clr[i]==-1) { if(!checkdfs(i))return false; } } return true; } void solve() { cin>>v; if(v==0)return; cin>>e; // memset(vis,0,sizeof(vis)); for(ll i=0; i<e; i++) { ll x,y; cin>>x>>y; g[x].pb(y); g[y].pb(x); } if(checkbi())cout<< "BICOLORABLE."<<endl; else cout<< "NOT BICOLORABLE."<<endl; } int main() { while(1) { solve(); memset(clr,-1,sizeof(clr)); } }