【題解】CSES 1668 Building Teams

【題目敘述】https://cses.fi/problemset/task/1668/
【解題想法】DFS

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, a, b, color[100005];
vector <int> v[100005];
 
void dfs(int x, int c){
    color[x] = c;
    for (int i:v[x]){
        if (color[i] == color[x]){
            cout << "IMPOSSIBLE\n";
            exit(0);
        }
        else if (!color[i]){
            if (color[x] == 1) dfs(i, 2);
            else dfs(i, 1);
        }
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++){
        if (!color[i]) dfs(i, 1);
    }
    for (int i = 1; i <= n; i++){
        cout << color[i] << " ";
    }
}
分享本文 Share with friends