Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector <vector<bool> > g;
- vector <bool> nodes, bio;
- bool solution=true, color=false;
- int dfs (int node) {
- color= color==false ? true : false;
- nodes[node]=color;
- for (int i=0;i<g[node].size();i++)
- if (g[node][i]==1 && bio[i]==false) {
- bio[i]=true;
- dfs (i); }
- color= color==false ? true : false;
- }
- void read (int n) {
- solution=true;
- int l;
- scanf ("%d", &l);
- nodes.clear (); g.clear (); bio.clear();
- nodes.resize (n, false);
- bio.resize (n, false);
- g.resize (n, nodes);
- for (int i=0;i<l;i++) {
- int a, b;
- scanf ("%d %d", &a, &b);
- g[a][b]=g[b][a]=true;
- }
- bio[0]=true;
- dfs (0);
- for (int i=0;i<n-1;i++) {
- for (int j=i+1;j<n;j++) {
- if (g[i][j]==true && nodes[i]==nodes[j]) solution=false; } }
- }
- int main () {
- //freopen ("readfile.in", "r", stdin);
- int n;
- while (scanf ("%d", &n)==1 && n!=0) {
- read (n);
- printf (solution==false ? "NOT BICOLORABLE.\n" : "BICOLORABLE.\n");
- }
- return 0; }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement