From ef69683807ba6d55189855d110bd3a5cf34a20e0 Mon Sep 17 00:00:00 2001 From: Aditya Naik Date: Sun, 13 May 2018 19:45:45 -0400 Subject: bicolor ugly (working) solution --- 10004/bicolor.cpp | 67 + 10004/bicolor.in | 3913 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 3980 insertions(+) create mode 100644 10004/bicolor.cpp create mode 100644 10004/bicolor.in diff --git a/10004/bicolor.cpp b/10004/bicolor.cpp new file mode 100644 index 0000000..3d2e404 --- /dev/null +++ b/10004/bicolor.cpp @@ -0,0 +1,67 @@ +#include +using namespace std; + +/* + +for any nodes a, b + if there exists c such that + c in a.PI AND c in b.PI: + NOT bicolorable + +for b in a.PI: + for j in b.PI: + if j in a.PI: + return false + +ABOVE ALGORITHM DOESNT WORK +cycles can consist of >=3 nodes (not bc when odd) + */ +bool findbc(int n, int adj[][200]); + +int main(){ + int n, e; + + cin>>n; + while(n){ + int adj[200][200]={0}, a, b; + cin>>e; + + for(int i=0; i>a>>b; + adj[a][b]=1; + adj[b][a]=1; + } + + bool bc = findbc(n, adj); + + if(!bc) cout<<"NOT BICOLORABLE.\n"; + else cout<<"BICOLORABLE.\n"; + + cin>>n; + }; +} + +bool findbc(int n, int adj[][200]){ + int clist[200]={0}; + clist[0]=1; + for(int i=0; i0) + clist[j]=clist[i]==1 ? 2:1; + else if(clist[i]==0 && clist[j]>0) + clist[i]=clist[j]==1 ? 2:1; + for(int i=0; i0) + clist[j]=clist[i]==1 ? 2:1; + else if(clist[i]==0 && clist[j]>0) + clist[i]=clist[j]==1 ? 2:1; + for(int i=0; i