Bridges Painting

题目描述

New Berland consists of $N$ islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 110;
int n, col[N][N];
vector <int> mp[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) {
int t; io > t;
while (t) mp[i].push_back(t), io > t;
}
}
void dfs(int t, int c) {
for (int i = 0; i < mp[t].size(); ++ i)
if (! col[t][mp[t][i]]) col[t][mp[t][i]] = col[mp[t][i]][t] = c, dfs(mp[t][i], c = 3 - c);
}
void process() {
for (int i = 1; i <= n; ++ i) if (mp[i].size() != 2) dfs(i, 1);
for (int i = 1; i <= n; ++ i) dfs(i, 1);
for (int i = 1; i <= n; ++ i) {
bool w = false, b = false;
for (int j = 0; j < mp[i].size(); ++ j) w |= col[i][mp[i][j]] == 1, b |= col[i][mp[i][j]] == 2;
if (mp[i].size() > 1 && ! (w && b)) { io < (char *) "No solution\n"; return; }
}
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < mp[i].size(); ++ j) io < col[i][mp[i][j]] < ' ';
io < 0 < '\n';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot