codeforces 522 A. Reposts

http://codeforces.com/problemset/problem/522/A 题意:给定某条消息的传播路径。问最远传播的距离。。 思路:其实就是问树的深度。。直接dfs就行了。。

存的时候用map<string,vector > mp;的方式存即可。

/* ***********************************************
Author :111qqz
Created Time :2015年12月05日 星期六 16时41分41秒
File Name :code/cf/problem/522A.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;



using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=2E2+7;
map<string,vector<string> > mp;
map<string,bool>vis;
string from,to,nouse;
int ans;
int n;

void dfs(string cur,int depth)
{
//    cout<<"cur:"<<cur<<" depth:"<<depth<<endl;
    vis[cur] = true;
    ans = max(ans,depth);
    for ( int i = 0 ; i < mp[cur].size() ; i++)
    {
	string v = mp[cur][i];
	if (!vis[v])
	    dfs(v,depth+1);
    }
}

string tran(string x)
{
    int len = x.length();
    for ( int i = 0 ; i < len ; i++)
    {
	if (x[i]>='A'&&x[i]<='Z')
	{
	    x[i] = char(x[i]+32);
	}
    }
    return x;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	mp.clear();
	scanf("%d",&n);
//	getchar();
	for ( int i = 0 ; i < n ; i++)
	{
	    cin>>to>>nouse>>from;
	    to = tran(to);
	    from = tran(from);
//	    getchar();
	//    cout<<"to:"<<to<<endl<<" nouse:"<<nouse<<endl<<" from:"<<from<<endl;
	    mp[from].push_back(to);
	}
	ans = 1;
	dfs("polycarp",1);
	printf("%d\n",ans);

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}