STABLE - VOI10 - Ổn định

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i,a,b)  for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define MAXN 10111
#define V vector<long>
#define PB push_back
using namespace std;

long n,m,s,cnt[MAXN],trace[MAXN],l[MAXN],q[2][MAXN],top[2];
V ke[MAXN];

void inp() {
    scanf("%ld %ld %ld",&n,&m,&s);
    FOR(i,1,m) {
        long u,v;
        scanf("%ld %ld",&u,&v);
        ke[u].PB(v);
    }
}

void solve() {
    top[0]=1; q[0][1]=s; cnt[s]=1; l[s]=1;
    long now=0;
    while (top[now]) {
        while (top[now]) {
            long u=q[now][top[now]--];
            FORV(v,ke[u])
            if (trace[*v]!=u)
                if (!l[*v]) {
                    trace[*v]=u;
                    cnt[*v]=cnt[u];
                    l[*v]=l[u]+1;
                    q[1-now][++top[1-now]]=*v;
                } else if (l[*v]==l[u]+1) {
                    trace[*v]=u;
                    cnt[*v]=min(2L,cnt[*v]+cnt[u]);
                }
        }
        now=1-now;
    }
    long res=0;
    FOR(i,1,n) if (cnt[i]==2) res++;
    cout<<res<<endl;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Download