Pagini recente » Cod sursa (job #1596217) | Cod sursa (job #1243576) | Statistici Costin Banu (costinbanu) | Cod sursa (job #2792221) | Cod sursa (job #2064673)
#include<fstream>
#include<vector>
#include<stack>
#define f first
#define s second
#define DIM 50005
using namespace std;
int n, m, i, j, x, y, nr, num, k, nod;
pair<int, int> vecin;
int c[DIM], e[3 * DIM], ff[4 * DIM], viz[DIM], g[DIM], viz2[DIM];
stack<int> s;
vector< pair<int, int> > v[DIM];
vector<int> w[DIM];
ifstream fin("johnie.in");
ofstream fout("johnie.out");
void dfs(int nod){
viz[nod] = 1;
c[++nr] = nod;
for(int i = 0; i < v[nod].size(); i++){
if(viz[ v[nod][i].f ] == 0){
dfs(v[nod][i].f);
}
}
}
int main(){
fin>> n >> m;
for(i = 1; i <= m; i++){
fin>> x >> y;
g[x]++;
g[y]++;
v[x].push_back( make_pair(y, i) );
v[y].push_back( make_pair(x, i) );
}
for(i = 1; i <= n; i++){
if(viz[i] == 0){
nr = 0;
dfs(i);
if(nr == 1){
num++;
w[num].push_back(i);
continue;
}
for(j = 1; j <= nr; j++){
if(g[ c[j] ] % 2 == 1){
g[ c[j] ]++;
g[n + 1]++;
m++;
v[ c[j] ].push_back( make_pair(n + 1, m) );
v[n + 1].push_back( make_pair(c[j], m) );
}
}
if(g[n + 1] == 0){
g[n + 1] = 2;
g[ c[1] ] += 2;
m += 2;
v[n + 1].push_back( make_pair(c[1], m - 1) );
v[n + 1].push_back( make_pair(c[1], m) );
v[i].push_back( make_pair(n + 1, m - 1) );
v[i].push_back( make_pair(n + 1, m) );
}
k = 0;
s.push(n + 1);
while(!s.empty()){
nod = s.top();
if(g[nod] == 0){
e[++k] = nod;
s.pop();
}
else{
while(ff[ v[nod][ v[nod].size() - 1].s ]){
v[nod].pop_back();
}
vecin = v[nod][ v[nod].size() - 1];
g[nod]--;
g[vecin.f]--;
ff[vecin.s] = 1;
v[nod].pop_back();
s.push(vecin.f);
}
}
for(j = 1; j < k; j++){
if(e[j] == n + 1){
num++;
}
else{
w[num].push_back(e[j]);
}
}
v[n + 1].clear();
}
}
fout<< num <<"\n";
for(i = 1; i <= num; i++){
fout<< w[i].size() <<" ";
for(j = 0; j < w[i].size(); j++){
fout<< w[i][j] <<" ";
}
fout<<"\n";
}
}