2011成都网赛 / 1009 - The Social Network

梦里梦外; 2021-12-19 17:04 147阅读 0赞

一眼就看出是水题，相当清晰。但是比赛的时候RE了一次。应该是错在输入的名字总数上界应该是2\*n 而不是n，把上界调大就A了。

代码：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<map>
    #include<queue>
    #include<algorithm>
    #include<string>
    using namespace std;
    
    #define MAXN 1010*2
    vector<int> G[MAXN];
    string a[MAXN];				//存名字
    map<string, int>vis;
    int num;
    int n, m;
    
    int vv[MAXN];		//访问标记
    queue<int> q;
    
    
    int addvec(string x)
    {
    	if(vis[x]) {return vis[x]; }
    	else
    	{
    		vis[x] = num;	a[num++] = x;	return num-1;
    	}
    }
    
    int getnum(string x) { return vis[x]; }
    
    void clear()
    {
    	for(int i=0; i<=n*2; i++)	if(!G[i].empty())
    	{
    		G[i].clear();
    	}
    }
    
    string ans[MAXN];
    int cnt[MAXN];
    int bfs(int x)
    {
    	int ansn=0;
    	int find=0;
    	memset(vv, 0, sizeof(vv));
    	memset(cnt, 0, sizeof(cnt));
    	vv[x] = 1;
    	for(int i=0; i<(int)G[x].size(); i++)	if(!vv[G[x][i]])
    	{
    		int v = G[x][i];
    		vv[v] = 1;
    		q.push(v);
    	}
    	int maxx=0;
    	while(!q.empty())
    	{
    		int u = q.front();	q.pop();
    		for(int i=0; i<(int)G[u].size(); i++) if(!vv[G[u][i]])
    		{
    			int v = G[u][i];
    			if(!cnt[v]) 
    			{
    				cnt[v]=1;
    				maxx = max(maxx, cnt[v]);
    				ans[ansn].clear();
    				ans[ansn++] += a[v];
    			}
    			else
    			{
    				cnt[v]++;
    				maxx = max(maxx, cnt[v]);
    			}
    			find = 1;
    		}
    	}
    	sort(ans, ans+ansn);
    	int flag=0;
    	for(int i=0; i<ansn; i++)
    	{
    		if(cnt[getnum(ans[i])] != maxx) continue;
    		if(flag) { cout<<" "; }
    		flag=1;
    		cout<<ans[i];
    	}
    	return find;
    }
    
    void solve()
    {
    	for(int i=0; i<m; i++)
    	{
    		string t;	cin>>t;
    		if(bfs(getnum(t)))
    		{
    			cout<<endl;
    		}
    		else cout<<"-"<<endl;
    	}
    }
    
    int main()
    {
    	int t;	cin>>t;
    	for(int i=0; i<t; i++)
    	{
    		printf("Case %d:\n", i+1);
    		
    		num=1;
    		if(!vis.empty()) vis.clear();
    		clear();
    
    		cin>>n>>m;
    		for(int j=0; j<n; j++)
    		{
    			string t1, t2;
    			cin>>t1>>t2;
    
    			int u = addvec(t1);
    			int v = addvec(t2);
    			G[u].push_back(v);
    			G[v].push_back(u);
    		}
    		solve();
    	}
    }

转载于:https://www.cnblogs.com/tclh123/archive/2011/09/11/2587067.html