Codeforces Round #518 (Div. 2)C. Colored Rooks
题意
给出n个颜色种类,m种颜色关系,要求在的方格中正确摆放这些颜色,每种颜色的个数不限。然后按顺序输出每种颜色的个数和所放的坐标。
要满足三个条件:
- 对于每种颜色,必须要有一个。
- 每种颜色都必须相连。
- 对于有关系的颜色必须相连,没关系的不能相连。
相连的定义是: 不同种类的颜色,只要在同一行或者同一列,就叫做相连。
题解
这题的答案不唯一,有一个简单的方法就是每个颜色分配一行,然后有关系的就在同一列上加颜色,一直顺次往后。
例如和1有关系的颜色是2,3,4。
和2有关系的颜色是2,4。
和3有关系的颜色是4。
代码
#include <bits/stdc++.h>
using namespace std;
int G[105][105];
int p,n,m;
struct node {
int x,y;
};
vector<node> v[105];
void solve() {
for(int i = 1; i <= n; ++i) {
v[i].push_back((node){i,p});
p++;
for(int j = i+1; j <= n; ++j) {
if(G[i][j]) {
v[i].push_back((node){i,p});
v[j].push_back((node){j,p});
p++;
}
}
}
}
int main() {
cin >> n >> m;
p = 1;
for(int i = 0; i < m; ++i) {
int u,v;
cin >> u >> v;
G[u][v] = G[v][u] = 1;
}
solve();
for(int i = 1; i <= n; ++i) {
cout << v[i].size() << endl;
for(int j = 0; j < v[i].size(); ++j) {
cout << v[i][j].x <<" " << v[i][j].y << endl;
}
}
return 0;
}