d768 - 10004 - Bicoloring
題目描述
題目要求判斷給定的無向圖是否為二分圖，即是否能用兩種顏色對圖的節點進行染色，使得相鄰的節點顏色不同。
解題思路
使用深度優先搜尋 (DFS) 演算法來判斷圖是否為二分圖。首先，初始化所有節點的顏色為 0 (未染色)。然後，從一個未染色的節點開始，將其染成顏色 1，並使用 DFS 遍歷其相鄰節點。對於每個相鄰節點，如果未染色，則將其染成與當前節點不同的顏色 (即顏色 3 - 當前節點的顏色)。如果相鄰節點已經染色，並且顏色與當前節點相同，則說明圖不是二分圖，直接返回 false。如果 DFS 遍歷完成後沒有發現任何衝突，則說明該連通分量是二分圖。由於題目保證圖是強連通的，因此只需要從一個節點開始 DFS 即可。
複雜度分析
- 時間複雜度: O(V + E)，其中 V 是節點的數量，E 是邊的數量。因為 DFS 遍歷了圖的所有節點和邊。
- 空間複雜度: O(V)，主要用於儲存顏色陣列
b和 DFS 的遞迴堆疊。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int a[201][201],n,m,b[201];
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void draw(int it){
if(b[it]==1){
for(int i=0;i<n;++i){
if(a[i][it]&&b[i]==0){
b[i]=2;
draw(i);
}
}
}
else{
for(int i=0;i<n;++i){
if(a[i][it]&&b[i]==0){
b[i]=1;
draw(i);
}
}
}
}
inline int chat(int it){
int color=b[it];
if(color==0)return 1;
for(int i=0;i<n;++i){
if(a[i][it]&&b[i]==color&&i!=it){
return 1;
}
}
return 0;
}
int main(){
while(n=read()){
m=read();
for(int i=0;i<n;++i){
b[i]=0;
for(int j=0;j<n;++j){
a[i][j]=0;
}
}
int x,y,ans=1;
while(m--){
x=read();
y=read();
a[x][y]=1;
a[y][x]=1;
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(a[i][j]){
b[i]=1;
draw(i);
i=n;
j=n;
}
}
}
for(int i=0;i<n;++i){
if(chat(i)){
ans=0;
}
}
if(ans||n<=2){
puts("BICOLORABLE.");
}
else{
puts("NOT BICOLORABLE.");
}
}
}