给定一个具有n个顶点的图。要给图上每个顶点染色,并且要使相邻的顶点颜色不同,是否能最多用2种颜色进行染色?
输入格式:输入第一行是两个正整数v和n,v是图中顶点数,n是图中边数。随后的n行,每行有两个正整数,分别是边的两个顶点编号。
输出格式:输出“Yes”或“No”
输入样例:在这里给出一组输入。例如:
3 30 10 21 2 输出样例:在这里给出相应的输出。例如:
No 输入样例:在这里给出一组输入。例如:
4 40 10 31 22 3 输出样例:在这里给出相应的输出。例如:
Yes 解题:使用BFS vis数组存放是否访问过,color存放每个点的颜色.,先把起点染色再入队,然后再遍历与之相邻的点,没访问过的就染色,访问过的就判断其与之颜色是否相同,相同则返回false;
#include<iostream>#include<vector>#include<queue>using namespace std;class Graph{public :int N,E;int type;vector<vector<int> > g;Graph(int N=0,int E=0,int type=0){this->N=N;this->E=E;this->type=type;this->g=vector<vector<int> >(N+1,vector<int>(N+1,0));}print(){for(int i=0;i<=N;i++){for(int j=0;j<=N;j++){cout<<g[i][j]<<" ";}cout<<endl;}}add(int v,int d,int w){g[v][d]=w;if(type==1){g[d][v]=w;}}};Graph g;bool bfs(int v){int vis[g.N]={0};int color[g.N]={0};queue<int> q;q.push(v);color[v]=0;while(!q.empty()){v=q.front();q.pop();if(vis[v]==0){vis[v]=1;for(int i=0;i<g.N;i++){if(g.g[v][i]==1){if(vis[i]==0){color[i]=color[v]==0?1:0;q.push(i);}else if(color[v]==color[i]){return false;}}}}}return true;}int main(void){int n,v;//顶点数 边数cin>>n>>v;g=Graph(n,v,1);for(int i=0;i<v;i++){int v,d;cin>>v>>d;g.add(v,d,1);}//g.print();cout<<bfs(0);return 0;}