Cod sursa(job #1346604)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 18 februarie 2015 13:59:05
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
/// markon
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define pb push_back
#define NMax 500005

using namespace std;

ifstream f("markon.in");
ofstream g("markon.out");

int n, m, X;
vector<int> V[NMax];
queue<int> C;
bool viz[NMax];
int val[NMax];
int nemarc[NMax];
vector<int> sol;

void read() {
    f>>n>>m>>X;
    for (int i=1;i<=n;i++)
        f>>val[i];
    for (int i=1;i<=m;i++) {
        int x,y;
        f>>x>>y;
        V[x].pb(y);
        V[y].pb(x);
        if (x != X && y != X) {
            nemarc[x]++;
            nemarc[y]++;
        }
    }
}

void solve() {
    C.push(X);
    viz[X] = true;
    sol.pb(X);

    while (!C.empty()) {
        int nod = C.front();
        cout<<nod;
        char chr;
        while(!(f>>noskipws>>chr));
        C.pop();

        for (unsigned i=0;i<V[nod].size();i++) {
            int vecin = V[nod][i];
            if (val[nod] == 0 || val[nod] > nemarc[nod] && !viz[vecin]) {
                nemarc[nod]--;
                viz[vecin] = true;
                C.push(vecin);
                sol.pb(vecin);
            }
        }
    }
}

void print() {
    g<<sol.size()<<'\n';
    for (auto it = sol.begin(); it != sol.end(); it++)
        g<<(*it)<<'\n';
}

int main() {

    read();
    memset(viz, false, sizeof(viz));
    solve();
    print();

    f.close(); g.close();
    return 0;
}