Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int t;
- int main(){
- // freopen("coverit.in", "r", stdin);
- cin >> t;
- while(t--){
- int n, m;
- cin >> n >> m;
- vector<vector<int>> adj(n+1);
- for(int i=0; i<m; i++){
- int a, b;
- cin >> a >> b;
- adj[a].push_back(b);
- adj[b].push_back(a);
- }
- /*
- breadth first search to label the color where all of the values
- are connected originally but we need to link the values and label
- the color of 0 or 1 which the value we are currently on is opposite
- of the value we are going to link it to so 0 would be 1 and 1 would
- be 0
- */
- queue<int> q;
- q.push(1);
- vector<int> color(n+1, -1);
- color[1] = 0;
- while(!q.empty()){
- int x = q.front();
- q.pop();
- for(int y: adj[x]){
- if(color[y] == -1){
- color[y] = color[x]^1;
- q.push(y);
- }
- }
- }
- /*
- after bfs we need to find which color has a smaller value because we know
- we can use the values from that color to link it to every other value and
- we need to chose the color which has a smaller amount and then we just
- print the amount and print the indexes with the color we are using
- */
- int c0 = count(color.begin(), color.end(), 0);
- int c1 = n-c0;
- if(c0<=c1){
- cout << c0 << '\n';
- string s = "";
- for(int i=1; i<=n; i++){
- if(color[i] == 0){
- cout << s << i;
- s = " ";
- }
- }
- cout << '\n';
- }else{
- cout << c1 << '\n';
- string s = "";
- for(int i=1; i<=n; i++){
- if(color[i] == 1){
- cout << s << i;
- s = " ";
- }
- }
- cout << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
