codeforces 522 A. Reposts

2015年12月5日 0 作者 CrazyKK

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

存的时候用map<string,vector<string> > 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;
}

/* ***********************************************

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;

}

分类目录codeforces

标签dfs map

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！