分析
用一个结构体记录每个节点的子目录集合和子文件集合。
注意可能会有重名的目录或文件出现,此时应该用一个带有层数的哈希表数组进行存储,防止有重名影响到命名情况。
最后用dfs输出答案。
最后一个点超时 ( ⊙ x ⊙ )
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N =1e5;
struct node{
string name;
set<string> dir,fil;
}fi[N];
unordered_map<string,int> mp[N]; //哈希表数组存储每个文件或目录的下标
int n,ma,tot;
void dfs(int u,string name)
{
if(u>ma) return ;
for(auto x:fi[mp[u][name]].dir)
{
for(int i=0;i<=u;i++) cout<<" ";
cout<<x<<endl;
int j=mp[u+1][x];
dfs(u+1,x);
}
if(fi[mp[u][name]].fil.size())
for(auto x:fi[mp[u][name]].fil)
{
for(int i=0;i<=u;i++) cout<<" ";
cout<<x<<endl;
}
}
int main()
{
mp[0]["root"]=0;
fi[0].name="root";
scanf("%d",&n);
char str[300];
for(int i=1;i<=n;i++)
{
scanf("%s",str);
int len=strlen(str);
int lt=0,cnt=0;
if(str[len-1]!='\\') lt=1;
string temp,tt="root";
for(int j=0;j<len;j++)
{
if(str[j]!='\\') temp+=str[j];
else{
fi[mp[cnt][tt]].dir.insert(temp); //类型为目录,加入目录集合
cnt++;
ma=max(ma,cnt);
if(!mp[cnt][temp])
{
mp[cnt][temp]=++tot;
fi[tot].name=temp;
}
tt=temp;
temp="";
}
}
if(temp.size()){ //最后一个可能类型为文件,加入文件集合
fi[mp[cnt][tt]].fil.insert(temp);
if(!mp[cnt][temp])
{
mp[cnt][temp]=++tot;
fi[tot].name=temp;
}
tt=temp;
ma=max(ma,cnt+1);
}
}
cout<<"root"<<endl;
dfs(0,"root");
return 0;
}