Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int graph[105][105]= {0},i,j,n,k,mx;
- vector<int>store,res;
- bool color[105];
- bool isblack(int node)
- {
- for(i=1; i<=node; i++)
- {
- if(graph[node][i]==1 && color[i]==true)
- {
- return false;
- }
- }
- return true;
- }
- void graphclr(int nodenum)
- {
- if(nodenum>n)
- {
- if(mx<store.size())
- {
- mx=store.size();
- res=store;
- }
- return;
- }
- if(isblack(nodenum)==true)
- {
- color[nodenum]=true;
- store.push_back(nodenum);
- graphclr(nodenum+1);
- store.pop_back();
- color[nodenum]=false;
- }
- graphclr(nodenum+1);
- }
- int main()
- {
- int t,x,y;
- cin>>t;
- while(t--)
- {
- memset(graph,0,sizeof(graph));
- memset(color,0,sizeof(color));
- store.clear();
- res.clear();
- cin>>n>>k;
- for(i=0; i<k; i++)
- {
- cin>>x>>y;
- graph[x][y]=1;
- graph[y][x]=1;
- }
- mx=0;
- graphclr(1);
- cout<<mx<<endl;
- for(i=0; i<mx; i++)
- {
- if(i>0)
- cout<<" ";
- cout<<res[i];
- }
- cout<<endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment