Cod sursa(job #2064673)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 12 noiembrie 2017 17:51:11
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.8 kb
#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";
    }
}