【LG P1738】洛谷的文件夹

P1738 洛谷的文件夹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

简析

显而易见这是一个求一个树一共有多少个节点的问题。

圆圈代表点，每个点有两个属性：一个是自己名字，一个是下级文件夹。

那么我们从根节点寻找。对于每个节点，先找他的兄弟有没有符合要求的当前级名字，如果有，转到该兄弟的孩子节点上；如果没有，那就新建一个，计数器 (+1)。

代码

#include<bits/stdc++.h>
using namespace std;
struct fold {
	string name;
	map<string,int> lst;
} a[200005];
int tot=0;
int main() {
	int n;
	scanf("%d",&n);
	int ans=0;
	for(int i=1; i<=n; i++) {
		string s;
		cin>>s,s+='/';
		string now;
		int k=0;
		for(int j=1; j<s.size(); j++) {
			if(s[j]^'/') {
				now+=s[j];
				continue;
			}
			if(!a[k].lst.count(now)) {
				ans++;
				a[k].lst[now]=++tot,a[tot].name=now;
			}
			k=a[k].lst[now];
//			cout<<now<<' '<<ans<<endl;//Debug
			now="";
		}
		printf("%d
",ans);
	}
	return 0;
}