Pagini recente » knird_llub | Cod sursa (job #2362331) | Cod sursa (job #724843) | Cod sursa (job #580940) | Cod sursa (job #1381298)
#include <fstream>
#include <vector>
#include <stack>
#include <map>
#define pii pair < int ,int >
#define fi first
#define se second
using namespace std;
const int NMAX = 100004;
ifstream f("victorie.in");
ofstream g("victorie.out");
stack < pii > St;
map < pii, bool > M;
vector < int > Graph[NMAX];
vector < vector < pii > > sol;
vector < vector < int > > s;
int level[NMAX] , n, low[NMAX], Root, use[NMAX], cnt[NMAX], apare[NMAX], pr[NMAX];
inline void Read(){
int m;
f >> n >> m;
for(int i=1;i<=m;++i){
int x, y;
f >> x >> y;
if(x>y)
swap(x,y);
if(x!=y && M.find(make_pair(x,y))==M.end()){
Graph[x].push_back(y);
Graph[y].push_back(x);
M[make_pair(x,y)]=1;
}
}
f.close();
}
inline vector < pii > Solve(const pii a){
vector < pii > ret;
while(St.top()!=a)
{
ret.push_back(St.top());
St.pop();
}
ret.push_back(a);
St.pop();
return ret;
}
inline void DFS(const int node,const int Father,const int niv){
int cnt = 0;
level[node] = niv;
low[node] = niv;
for(vector < int >::iterator it = Graph[node].begin(); it != Graph[node].end(); ++it){
int x = *it;
if(x==Father)
continue;
if(level[x]==0){
St.push(make_pair(node,x));
DFS(x,node,niv+1);
low[node] = min(low[node],low[x]);
if(low[x] >= niv){
sol.push_back(Solve(make_pair(node,x)));
}
++cnt;
}
else
low[node] = min(low[node],level[x]);
}
if(cnt==0)
return ;
}
inline vector < int > Decodif(vector < pii > v){
vector < int >ret;
for(unsigned i = 0;i < v.size(); ++i){
if(!use[v[i].fi]){
ret.push_back(v[i].fi);
use[v[i].fi] = 1;
}
if(!use[v[i].se]){
ret.push_back(v[i].se);
use[v[i].se] = 1;
}
}
for(unsigned i = 0;i < ret.size(); ++i)
use[ret[i]] = 0;
return ret;
}
inline void Write(){
//g<<sol.size()<<"\n";
for(unsigned i = 0;i < sol.size(); ++i){
vector < int > v = Decodif(sol[i]);
for(unsigned j = 0;j < v.size(); ++j){
++cnt[v[j]];
}
/*for(unsigned j = 0;j < v.size(); ++j)
g<<v[j]<<" ";
g<<"\n";*/
s.push_back(v);
}
int number = 0;
for(unsigned i = 0;i < s.size(); ++i){
if(s[i].size()%2==0)
continue;
bool ok = 0;
for(unsigned j = 0;j < s[i].size() && ok == 0; ++j)
if(cnt[s[i][j]] >1)
ok = 1;
if(ok == 1)
for(unsigned j = 0;j < s[i].size(); ++j){
if(pr[s[i][j]]==0)
++number;
pr[s[i][j]] = 1;
}
}
g<<number<<"\n";
for(int i=1;i<=n;++i)
if(pr[i])
g<<i<<" ";
g<<"\n";
g.close();
}
int main()
{
Read();
Root = 1;
DFS(1,0,1);
Write();
return 0;
}