Thuật toán:
- Gọi b[] là dãy các giá trị của các counter.
- Ta sẽ nhấn counter thứ i nếu b[i] = a[i].
Và khi nhấn counter i thì ta xem các counter j kề i có giá trị b[j] sau khi tăng 1 có bằng a[j] không. Nếu bằng thì chắc chắn ta sẽ phải nhấn counter j, do đó ta bỏ counter j vào hàng đợi chờ đến lượt duyệt.
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#define oo 100005
#define rep(i,s,e) for(int i = s; i < e; i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
using namespace std;
typedef pair<int,int> II;
typedef pair<II,int> d;
typedef long long LL;
vector<int> V[oo];
map<int,int> M;
vector<int> res;
set<int> S;
queue<int> Q;
int n,m,u,v;
int a[oo],b[oo];
int main()
{
#define Off true
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
cin >> n >> m;
rep(i,1,m+1)
{
scanf("%d %d",&u,&v);
V[u].push_back(v);
V[v].push_back(u);
}
rep(i,1,n+1) scanf("%d",&a[i]);
rep(i,1,n+1)
if(a[i] == b[i]) Q.push(i);
while(!Q.empty())
{
int p = Q.front();
Q.pop();
if(a[p]!=b[p]) continue;
res.push_back(p);
FOR(it,V[p])
if(++b[*it] == a[*it]) Q.push(*it);
}
printf("%d\n",SZ(res));
rep(i,0,SZ(res))
printf("%d ",res[i]);
return 0;
}
Không có nhận xét nào:
Đăng nhận xét