Bad Horse -google-判断是否是二分图

Problem

As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn't about to spend his valuable time figuring out how to split the League members by himself. That what he's got you -- his loyal henchman -- for.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a positive integer M on a line by itself -- the number of troublesome pairs of League members. The next M lines each contain a pair of names, separated by a single space.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "Yes" or "No", depending on whether the League members mentioned in the input can be split into two groups with neither of the groups containing a troublesome pair.

Limits

1 ≤ T ≤ 100.
Each member name will consist of only letters and the underscore character.
Names are case-sensitive.
No pair will appear more than once in the same test case.
Each pair will contain two distinct League members.

Small dataset

1 ≤ M ≤ 10.

Large dataset

1 ≤ M ≤ 100.

Sample

推荐指数：※※※

来源：google

可以转换成典型的判断是否是二分图问题。

BFS采用图着色。如果两个颜色可以，这是二分图，否则不是。

注意多个不连通子图的情况

二分图相关问题：http://blog.csdn.net/zhu_liangwei/article/details/11488809

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<map>
#include<queue>
#include<string>
using namespace std;
const int T=201;
int
color[T],visited[T];
int bfs(int index,vector<vector<int> > *adj,int n){
int i,j;
memset(color,-1,sizeof(color));
memset(visited,0,sizeof(visited));
queue<int >q;
q.push(index);
visited[index]=true;
color[index]=0;
while(!q.empty()){
int tmp_now=q.front();
for(i=0;i<(*adj)[tmp_now].size();i++){
int tmp_index=(*adj)[tmp_now][i];
if(color[tmp_index]==-1){
color[tmp_index]=(color[tmp_now]+1)%2;
q.push(tmp_index);
visited[tmp_index]=true;
}
else if(color[tmp_index]==color[tmp_now]&&tmp_index!=tmp_now)//color is same and is a new node
return false;
}
q.pop();
}
for(i=0;i<n;i++){
if(visited[i]==false){
return bfs(i,adj,n);
}
}
return true;
}
int main()
{
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
int loops;
scanf("%d",&loops);
int casenum;
for(casenum=1;casenum<=loops;casenum++){
int pairs,i;
scanf("%d",&pairs);
vector<vector<int> >adj;
adj.resize(T);
map<string,int> mp;
int m_id=0;
for(i=0;i<pairs;i++){
string a,b;
int tmp_a,tmp_b;
cin>>a>>b;
if(mp.count(a)>0){//hash
tmp_a=mp[a];
}
else{
mp[a]=m_id;
tmp_a=m_id;
m_id++;
}
if(mp.count(b)>0){//hash
tmp_b=mp[b];
}
else{
mp[b]=m_id;
tmp_b=m_id;
m_id++;
}
adj[tmp_a].push_back(tmp_b);
adj[tmp_b].push_back(tmp_a);
}
if(bfs(0,&adj,m_id)==true)
printf("Case #%d: Yesn",casenum);
else
printf("Case #%d: Non",casenum);
}
return 0;
}

最后

以上就是天真面包为你收集整理的Bad Horse -google-判断是否是二分图的全部内容，希望文章能够帮你解决Bad Horse -google-判断是否是二分图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。