牛客20180601练习赛19 E

牛客20180601练习赛19 E

题目描述

已知第i个瓶子的品牌为ai,且其能打开bi品牌的瓶子.
问有几瓶饮料托米无法喝到.
被用于打开饮料瓶的瓶子不一定需要被打开.
一个瓶子不能打开其本身.
输入描述:
第一行一个整数n,表示饮料的瓶数.
接下来n行,每行两个整数ai,bi.
输出描述:
输出一行一个整数,表示小托米无法喝到的饮料瓶数.

示例1
输入
4
1 1
2 2
3 3
4 4
输出 4

示例2
输入
4
1 2
2 3
3 4
4 1
输出 0

备注:
1≤n≤100
1≤ ai,bi≤ 1000。

分析

一道水题，可开三个数组，维护瓶盖，瓶子，这个瓶子是否被打开过，暴力解题即可，时间：3ms。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int ans,al[200],bl[200],cl[200],n;
void dfs(int a){for(int i=1;i<=n;i++){if(a==i) continue;if(cl[i]) continue;if(al[i]==bl[a]) ans++,cl[i]=1,dfs(i);}
}
int main(){memset(al,0,sizeof(al));memset(cl,0,sizeof(cl));memset(bl,0,sizeof(bl));scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&al[i],&bl[i]);for(int i=1;i<=n;i++) dfs(i);printf("%dn",n-ans);return 0;
}