# UVa 11080

## Summary

Its a simple bipartite graph Problem...like as UVA 10004.

## Explanation

If Its not BiGraph print -1;

## Notes

"Help the king to find the Minimum Number of guards needed to guard all the junctions and streets of his country."

## Implementations

Notes/Hints on actual implementation here.

on approach for bicoloring (determine the graph is bipartite or not ) is use BFS method.

see this sample solution for this problem :

```int BFS(int s)
{
queue<int> q;
q.push(s);
color[s]=1;
int tot=0,black=0;

while (!q.empty()){
int u=q.front();
q.pop();
tot++;
if (color[u]==1)black++;

if (color[v]==2){
color[v]=1-color[u];
q.push(v);
}
else if (color[v]==color[u]) return -1; //means conflict and it's imposible
}

}
if (tot==1) return 1;//if it's a isolated vertex we should guard this by one person
return min(black,tot-black);//choose least color used
}
```

and in main method of your code such checking should be use :

```for (int i=0;i<N && !impos;i++)
if (color[i]==2){
int x=BFS(i);
if (x==-1)impos=true;
else ans+=x;

}
```

## Optimizations

Optimizations here.

```5
5 1
0 1
5 0
1 0
4 2
0 1
2 3
5 5
0 1
1 2
2 3
0 4
3 4
```

```4
5
1
2
-1
```

## References

SystemDown

Categories here, use the form [[Category:UVa Online Judge|11080]] [[Category: Category Name]], see Categories for a list