首页 > 代码库 > POJ 3256 Cow Picnic 搜索
POJ 3256 Cow Picnic 搜索
题目大意:有一些奶牛在一些牧场里,这些牧场有些单向边,牧场中的牛按照单向边行走,问有哪些牧场所有牛都能到达。
思路:图的连通性本来应该是tarjan或者并查集什么的,但是这个题数据范围是在是太弱了,所以就搜索就行了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 10010 using namespace std; int cows,points,edges; bool have_cow[MAX]; int head[MAX],total; int next[MAX],aim[MAX]; bool v[MAX]; int cnt[MAX],blocks; inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void DFS(int x) { if(v[x]) return ; cnt[x]++; v[x] = true; for(int i = head[x]; i; i = next[i]) DFS(aim[i]); } int main() { cin >> cows >> points >> edges; for(int x,i = 1; i <= cows; ++i) { scanf("%d",&x); if(!have_cow[x]) have_cow[x] = true,++blocks; } for(int x,y,i = 1; i <= edges; ++i) { scanf("%d%d",&x,&y); Add(x,y); } for(int i = 1; i <= points; ++i) if(have_cow[i]) { memset(v,false,sizeof(v)); DFS(i); } int ans = 0; for(int i = 1;i <= points; ++i) if(cnt[i] == blocks) ans++; cout << ans << endl; return 0; }
POJ 3256 Cow Picnic 搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。