zzulioj--1831-- 周末出游(vector建图+dfs)

1831: 周末出游

Time Limit: 1 Sec  Memory Limit:
128 MB

Submit: 22  Solved: 8



SubmitStatusWeb
Board

Description

周末天气真好，大家组织一起出去玩（玩你妹，不好好学习），可是，有些人要知道（有好朋友了不起呀）自己最要好的朋友接受邀请了，他才会去，只有邀请到他们最好的朋友才会去（贱人就是矫情）。可是作为负责人的你（冤大头）必须判断是否能够办好这次聚会（气死爸爸拉，哼），邀请到所有的人。

Input

每组第一行输入n，表示有n个人。然后第二行输入n个数a1，a2，a3.....(0<ai<=n)表示第i个人的希望自己的那位好朋友要去。如果ai=i表示这位同学一定会去（注孤）。(0<n<1000)

Output

如果能邀请到所有输出yes，反之no。

Sample Input

41 2 3 3

Sample Output

yes

HINT

刚开始想的太麻烦了，以为还可以邀请一个人，后来才发现折磨简单

#include<stdio.h>

#include<string.h>

#include<vector>

#include<algorithm>

using namespace std;

vector<int>g[10010];

int vis[10010];

int ans;

void dfs(int u)

{

	for(int i=0;i<g[u].size();i++)

	{

		ans++;

		dfs(g[u][i]);

	}

}

int main()

{

	int n;

	while(scanf("%d",&n)!=EOF)

	{

		memset(vis,0,sizeof(vis));

		ans=0;

		int a;

		for(int i=0;i<=n;i++)

		g[i].clear();

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&a);

			if(a==i)

			{

				vis[a]=1;

			}

			else

			g[a].push_back(i);

		}

		for(int i=1;i<=n;i++)

		if(vis[i])

		{

			ans++;

			dfs(i);

		}

		if(ans==n)

		printf("yes\n");

		else

		printf("no\n");

	}

	return 0;

}