Better man

改变性格 改变命运！

 

强连通分支 USACO schlnet

 1#include<iostream>
 2using namespace std;
 3int n;
 4bool map[101][101];
 5bool visit[101];
 6int tme=0;
 7int order[101];
 8int tree[101];
 9int in[101],out[101];
10void dfs(int k)
11{
12    visit[k]=1;
13    for(int i=1;i<=n;++i)
14        if(!visit[i]&&map[k][i])
15            dfs(i);
16    order[tme++]=k;
17}
18void search(int k,int num)
19{
20    visit[k]=1;
21    tree[k]=num;
22    for(int i=1;i<=n;++i)
23        if(!visit[i]&&map[i][k])
24            search(i,num);
25}
26void solve()
27{
28    memset(visit,0,sizeof(visit));
29    for(int i=1;i<=n;++i)
30        if(!visit[i])
31            dfs(i);
32    memset(visit, 0, sizeof(visit));
33    int num=0;
34    //按时间戳的顺序搜索
35    for(int i=tme-1;i>=0;--i)
36    {
37        if(!visit[ order[i] ])
38            search(order[i],++num);
39    }
40    for(int i=1;i<=n;++i)
41    {
42        int t1=tree[i];
43        for(int j=1;j<=n;++j)
44        {
45            int t2=tree[j];
46            if(t1!=t2&&map[i][j])
47            {
48                in[t2]++;
49                out[t1]++;
50            }
51        }
52    }
53    int ans1=0,ans2=0;
54    for(int i=1;i<=num;++i)
55    {
56        if(in[i]==0)ans1++;
57        if(out[i]==0)ans2++;
58    }
59    if(num==1)printf("1\n0\n");
60    else printf("%d\n%d\n",ans1,max(ans1,ans2));
61}
62int main()
63{
64    tme=0;
65    freopen("schlnet.in","r",stdin);
66    freopen("schlnet.out","w",stdout);
67    scanf("%d",&n);
68    int tmp;
69    for(int i=1;i<=n;++i)
70        while(scanf("%d",&tmp)&&tmp)
71            map[i][tmp]=1;
72    solve();
73    return 0;
74}
75

posted on 2009-01-27 22:58 SHFACM 阅读(177) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(2)

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜