POJ-3256, TJU-2834:Cow Picnic

keyword

有向グラフ　探索　C++

概要

牛がk(<100)匹いて、それぞれ(n<1000)個の牧草地のどこかにいる。m(<10000)の有向辺が与えられる。このとき、全ての牛が到達できるような牧草地がいくつあるかを求める問題。それぞれの牛について到達可能な点を探索してやればよい。計算量はO(k*m)なので一応間に合う。一回計算したのを再利用とかしたらもっと早くなる、かもしれない。最初は問題を勘違いして2部グラフのマッチングだと思っていた。

int main(){
    bool visited[1002], all[1002];
    int k,n,m,i,j,x,y;
    int st[102];
    scanf("%d%d%d",&k,&n,&m);
    REP(i,1002)all[i]=false;
    REP(i,n) all[i] = true;

    vector< vector<int> > graph(n);
    REP(i,k){
        scanf("%d",&x);
        st[i] = x - 1;
    }
    REP(i,m){
        scanf("%d%d",&x,&y);
        graph[x-1].PB(y-1);
    }

    REP(i,k){
        int cur = st[i];
        REP(j,n) visited[j] = false;
        visited[cur] = true;
        queue<int> Q;
        Q.push(cur);
        while(!Q.empty()){
            cur = Q.front(); Q.pop();
            visited[cur] = true;
            EACH(graph[cur],it)if(!visited[*it]){
                Q.push(*it);
            }
        }
        REP(j,n) if(!visited[j]) all[j] = false;
    }

    printf("%d\n",count(all,all+n,true));
    //printf("%d\n",BipartiteMatchingByList(bigraph));

    return 0;
}