水题 水题 水题
染色
但有个限制条件 就是选出来的边要大于等于 m / 2
所以 再每次加入一个点的时候
判断与这个点相连的是黑色的多 还是白色的多
黑色的多就放到白色那边
反之亦然
保证每次加入点后保留的边的个数尽量多
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <list> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 105, INF = 0x7fffffff; vector<int> G[maxn]; int vis[maxn]; int n, m; int istwo(int u) { queue<int> E; E.push(u); vis[u] = 1; while(!E.empty()) { u = E.front(); E.pop(); for(int i=0; i<G[u].size(); i++) { int v = G[u][i]; if(vis[v] == -1) { int h1 = 0, h2 = 0; for(int j = 0; j < G[v].size(); j++) { if(vis[G[v][j]] == 0) h1++; else if(vis[G[v][j]] == 1) h2++; } if(h1 > h2) vis[v] = 1; else vis[v] = 0; E.push(v); } } } return 1; } vector<int> v1, v2; int main() { int T; rd(T); while(T--) { v1.clear(); v2.clear(); int u, v; rd(n), rd(m); for(int i = 0; i <= n; i++) vis[i]= -1, G[i].clear(); for(int i = 0; i < m; i++) { rd(u), rd(v); G[u].push_back(v); G[v].push_back(u); } for(int i = 1; i <= n; i++) if(vis[i] == -1) istwo(i); for(int i = 1; i <= n; i++) { if(vis[i] == 1) v1.push_back(i); else if(vis[i] == 0) v2.push_back(i); } int len1 = v1.size(); printf("%d", len1); for(int i = 0; i < v1.size(); i++) { printf(" %d", v1[i]); } printf(" "); int len2 = v2.size(); printf("%d", len2); for(int i = 0; i < v2.size(); i++) { printf(" %d", v2[i]); } printf(" "); } return 0; }