cf 1068 C
构造题
题意给你n个颜色 m个关系 颜色和颜色有关系就是他们在一行或者在一列 可以相邻
没关系就不能在一行 不能在一列 不能相邻
我们简单构造一下 你把vis[a][b]打上标记 有关系的你就填补行 用颜色作为他们的列
这样构造 换个关系就升行 点可以构造很多 所以这个做法就可以了 具体画画就出来了
#include <cstdio> #include <queue> #include <map> #include <iostream> #include <cstring> #include <algorithm> #include <stack> using namespace std; vector<pair<int ,int > > vt[105]; int vis[105][105],now[105]; int main(){ int n,m; scanf("%d%d",&n,&m); while(m--){ int a,b; scanf("%d%d",&a,&b); vis[a][b] = 1; } int tmp = 1; for(int i = 1;i<=n;++i){ for(int j = 1;j<=n;++j){ if(vis[i][j]){ vt[i].push_back(make_pair(tmp,i)); vt[j].push_back(make_pair(tmp,j)); now[i] = 1; now[j] = 1; tmp++; vis[i][j] = 0; } } } for(int i = 1;i<=n;++i){ if(!now[i]){ vt[i].push_back(make_pair(tmp,i)); tmp++; } } for(int i = 1;i<=n;++i){ if(vt[i].size()){ int sz= vt[i].size(); printf("%d\n",sz); for(vector<pair<int ,int > >::iterator iter=vt[i].begin();iter!=vt[i].end();iter++) { printf("%d %d\n",iter->first,iter->second); } } } return 0; }
