foj1229（和谐短信问题）

http://acm.fzu.edu.cn/problem.php?pid=1229
判断有N条边的有向图的环的个数！
要点：由于每个点只有一个出度，故给每个环都用特定的数值进行标记！

import java.util.*;

import java.io.*;

public class ACM_1229{

public static void main(String rgs[]) throws Exception

{

BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

String s =null;

while((s = stdin.readLine())!=null)

{

int i,j,k,n=Integer.parseInt(s),count=0;

int[] a=new int[n+1];

int[] b=new int[n+1];

int[] flag=new int[n+1];

s = stdin.readLine();

StringTokenizer st = new StringTokenizer(s);

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

a[i] = Integer.parseInt(st.nextToken());

flag[i]=0;

}

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

int p=i+1;

if(flag[i]==0){

j=i;

k=0;

do{

flag[j]=p;

k++;

b[j]=k;

j=a[j];

}while(flag[j]==0);

if(flag[j]==p)

count+=k+1-b[j];

}

System.out.println(count);

}

posted on 2010-09-26 20:58 飞翔天使阅读(219) 评论(0) 编辑收藏所属分类: foj

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 Chat2DB C++博客博问管理
相关文章: foj1490（五子棋） foj1229（和谐短信问题） foj1922（非主流）