Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- int n,m,l,r;
- bool ri=true;
- vector < vector <int> > g;
- vector <int> used,c;
- void input()
- {
- cin>>n>>m;
- g.resize(n+1);
- used.resize(n+1,0);
- c.resize(n+1);
- for(int i=1;i<m+1;i++)
- {
- cin>>l>>r;
- g[l].push_back(r);
- g[r].push_back(l);
- }
- }
- void dfs(int a)
- {
- used[a]=true;
- for(int i=0;i<g[a].size();i++)
- if(!used[g[a][i]])
- {
- c[g[a][i]]=1-c[a];
- dfs(g[a][i]);
- }
- else if (c[g[a][i]]==c[a])
- {
- ri=false;
- return;
- }
- }
- void bfs(int a)
- {
- queue <int > q;
- q.push(a);
- used[a]=1;
- c[a]=0;
- while(!q.empty())
- {
- int v=q.front();
- q.pop();
- for(int i=0;i<g[v].size();i++)
- if(!used[g[v][i]])
- { c[g[v][i]]=1-c[v];
- used[g[v][i]]=1;
- q.push(g[v][i]);
- }
- else if (c[g[v][i]]==c[v])
- {
- ri=false;
- return;
- }
- }
- }
- int main()
- { input();
- /*
- bfs(1); */
- c[1]=1;
- dfs(1);
- if(ri)
- {
- cout<<"YES"<<endl;
- for(int i=1;i<n+1;i++)
- if(c[i]==0) cout<<i<<" ";
- }
- else cout<<"NO.";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement