第一次用vector解得題,值得紀念,這道題是二染色問題,我用bfs解得,就是染色,判斷,計數問題,其
實挺簡單的,就是得判一下特殊情況,當n<2的時候就不能有解,因為題目要求每個組至少有一個人,當沒有不認識的
人的時候就是一個組是n-1,另一個組人數為1
上代碼:
#include#include #include #include #include #include using namespace std; int visit[100005]; int n,m,flag,ans1,ans2; vector v[100005]; int bfs(int x) { queue q; q.push(x); visit[x] = 1; while(!q.empty()) { int y = q.front(); q.pop(); if(visit[y] == 1) ans1++; else ans2++; for(int i=0; i