沈阳市于洪区建设局网站,做哈尔滨本地门户网站赚钱吗,公司网页宣传页面设计,wordpress 新浪图床题目描述 如图所示为某生态系统的食物网示意图#xff0c;据图回答第 1 小题 现在给你 n 个物种和 m 条能量流动关系#xff0c;求其中的食物链条数。物种的名称为从 1 到 n 编号 M 条能量流动关系形如 1,2,3,…,am−1,bm−1,am,bm。其中 ai 和 bi 表示能量从物…题目描述 如图所示为某生态系统的食物网示意图据图回答第 1 小题 现在给你 n 个物种和 m 条能量流动关系求其中的食物链条数。物种的名称为从 1 到 n 编号 M 条能量流动关系形如 1,2,3,…,am−1,bm−1,am,bm。其中 ai 和 bi 表示能量从物种 ai 流向物种 bi注意单独的一种孤立生物不算一条食物链。
输入格式
第一行两个整数 n,m接下来 m 行每行两个整数 ai 和 bi 描述 m 条能量流动关系。
输出格式
一个整数即食物网中的食物链条数。
输入输出样例
输入 #1复制
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9
输出 #1复制
9
说明/提示
数据保证输入数据符号生物学特点且不会有重复的能量流动关系出现题目保证答案不会爆 int。
对于 100%100% 的数据1≤N≤1000001≤m≤200000。
记忆化搜索 warn:first[x]0 (出度为0)
#includebits/stdc.h
using namespace std;
//#pragma GCC optimize(2)
#define endl \n
#define lowbit(x) ((x)-(x))
const int mod1e97;
typedef long long ll;
ll ans0,n1,m1;
ll t,s1,s2,s3,s4,max10,min1100000000,sum0,n,m,i,j,k,l,r;
ll u,v,w;
inline int read() {bool sym0;int res0;char chgetchar();while(!isdigit(ch))sym |(ch -),chgetchar();while(isdigit(ch)) res (res3)(res1)(ch^48),chgetchar();return sym ? -res : res;
}
void print(int x) {if(!x)return;print(x/10);putchar(x%100);
}
int isPrime(int n) {float n_sqrt;if(n1) return 0;if(n2 || n3) return 1;if(n%6!1 n%6!5) return 0;n_sqrtfloor(sqrt((float)n));for(int i5; in_sqrt; i6) {if(n%(i)0 | n%(i2)0) return 0;}return 1;
}ll anss[205205];
ll dp[205205],first[205005],vis[200005],cnt0;struct node{ll to,next,w;
}edges[400005];
void add(ll u,ll v){edges[cnt].to v;edges[cnt].next first[u];first[u]cnt;
}
ll dfs(ll x,ll fa){//没什么用的 fa cout first[x] ;if(first[x]0vis[x]!0)return 1; //first[x]的妙用(出度为0)即为一条链vis[x]判断是1否孤立(是否为根节点)即一个点 if(anss[x])//这个x点若搜过则直接返回即剪枝 return anss[x];for(ll ifirst[x];i;iedges[i].next){//遍历 ll vedges[i].to ;//if(vfa)
// continue;anss[x](anss[x]dfs(v,x));}return anss[x];//记忆化搜索
}
ll root;
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cinn;
cinm;
for(i1;im;i){cins1s2;add(s1,s2);//add(s2,s1);// 有向图 vis[s2];
}
for(i1;in;i){if(vis[i]0)// 找根节点 {ansdfs(i,-1);}
}
coutans;return 0;
}//mio lover
