題目鏈接：點擊查看
題目大意：給出一張圖，現在要求給出一種合適的染色方案，使得：
只能用 ' a ' , ' b ' , ' c ' 進行染色有邊相連的兩個點的顏色要么相同，要么相鄰，不能是 ' a ' 和 ' c '沒有邊相連的兩個點的顏色只能是 ' a ' 和 ' c '
題目分析：基于第三個條件，不難看出原圖的補圖如果不是一個二分圖時，答案一定是 No，因為無法處理所有情況三
而當原圖的補圖是一個二分圖時，相當于只滿足一個必要條件，還需要判斷一下情況二作為充分條件才行，只有同時滿足了情況二和情況三才能說明本題是有解的
然后就是一個小坑，這個題目中的原圖和補圖都不一定是一張連通圖，所以需要當多個連通圖依次處理才行
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=510;bool maze[N][N];vector<int>node[N];int c[N],n,m;char ans[N];bool vis[N];bool dfs(int u,int val)//二分圖染色
{c[u]=val;for(auto v:node[u]){if(c[v]!=-1){if(c[u]==c[v])return false;continue;}if(!dfs(v,val^1))return false;}return true;
}bool check(int u)//判斷情況二
{vis[u]=true;for(int i=1;i<=n;i++)if(maze[u][i]){if(abs(ans[u]-ans[i])>1)return false;if(!vis[i]&&!check(i))return false;}return true;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);memset(c,-1,sizeof(c));int rt=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);maze[u][v]=maze[v][u]=true;}for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)if(!maze[i][j]){node[i].push_back(j);node[j].push_back(i);}bool flag=true;for(int i=1;i<=n;i++)//對所有的連通塊進行二分圖染色，判斷情況三if(c[i]==-1&&node[i].size())flag&=dfs(i,0);if(flag){for(int i=1;i<=n;i++){if(c[i]==1)ans[i]='a';else if(c[i]==0)ans[i]='c';elseans[i]='b';}bool flag=true;for(int i=1;i<=n;i++)//對所有的連通塊判斷情況二flag&=check(1);if(flag)//同時滿足才是YES{puts("Yes");for(int i=1;i<=n;i++)putchar(ans[i]);puts("");}elseputs("No");}elseputs("No");return 0;
}
?
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生
總結
以上是生活随笔為你收集整理的CodeForces - 817F Graph and String(dfs判二分图)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
