2853——奶牛聚餐

K(1≤K≤100)只奶牛分散在N(1≤N≤1000)个牧场.现在她们要集中起来进餐.牧场之间有M(1≤M≤10000)条有向路连接,而且不存在起点和终点相同的有向路.她们进餐的地点必须是所有奶牛都可到达的地方.那么,有多少这样的牧场呢?

 第1行输入K,N,M.接下来K行,每行一个整数表示一只奶牛所在的牧场编号.接下来M行,每行两个整数,表示一条有向路的起点和终点

2 4 4
2
3
1 2
1 4
2 3
3 4

sample output:

2
牧场3,4是这样的牧场.

 

AC——code:

 

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

/* 整体思路:从每个奶牛所在的地方开始访问,每个节点若能被访问到,则对应的次数+1,如果某个节点次数为奶牛数,

则符合题目要求 */

struct nds{

    int y;

    int nxt;

};

struct edg{     //输入时,存边用

    int x;

    int y;

};

nds e[10005];

edg a[10005];

int lk[1005],sum;

int k,n,m,ltp;

int t1[105];

int f[1005];

int h[1005];//每次处理f数组结果时用

void ist(int x,int y){

    e[++ltp]={y,lk[x]};

    lk[x]=ltp;

}

void dfs(int x){

    if(f[x]) return ;

    f[x]=true;

    for(int i=lk[x];i;i=e[i].nxt){

        dfs(e[i].y);

    }

}

void fun(){

    for(int i=1;i<=n;i++){

        if(f[i])

            h[i]++;

    }

}

int main(){

    cin>>k>>n>>m;

    for(int i=1;i<=k;i++){

        cin>>t1[i];

    }

    for(int i=1;i<=m;i++){

        cin>>a[i].x;

        cin>>a[i].y;

    }

    for(int i=1;i<=m;i++){

        ist(a[i].x,a[i].y);

    }

    for(int i=1;i<=k;i++){

        if(t1[i]){

            dfs(t1[i]);

            fun();

            for(int i=1;i<1005;i++)

                f[i]=false;

        }

    }

    int p;

    for(int i=1;i<=1005;i++){

        if(h[i]==k){

            sum++;

        }

    }

    cout<<sum;

    cin>>p;

    return 0;

}

上一篇:2:Oracle体系结构(物理结构)


下一篇:自己DIY一个pinephone——debian与主线linux在红米2(msm8916)上的移植(一)