158 条题解

  • 3
    @ 2016-08-09 15:49:53
    记录信息
    评测状态    Accepted
    题目  P1022 Victoria的舞会2
    递交时间    2016-08-09 15:48:04
    代码语言    C++
    评测机 ShadowShore
    消耗时间    0 ms
    消耗内存    552 KiB
    评测时间    2016-08-09 15:48:06
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    Accepted, time = 0 ms, mem = 552 KiB, score = 100
    代码
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using std :: min;
    int n,m;
    bool s[201][201],v[201];
    void floyd() {
      for (int k = 1;k <= n;k++)
        for (int i = 1;i <= n;i++)
          for (int j = 1;j <= n;j++)
            if (s[i][k] && s[k][j]) s[i][j] = true;
    }
    int main() {
      memset(s,false,sizeof(s));
      scanf("%d",&n);
      int x;
      for (int i = 1;i <= n;i++)
        while (scanf("%d",&x),x != 0)
          s[i][x] = true;
      floyd();
      int ans = 0;
      memset(v,true,sizeof(v));
      for (int i = 1;i <= n;i++)
        if (v[i]) {
          for (int j = 1;j <= n;j++)
            if (j != i && s[i][j] && s[j][i])
              v[j] = false;
          ans++;
          v[i] = false;
        } 
      printf("%d",ans);
      return 0;
    }
    
  • 2
    @ 2016-11-14 21:31:44

    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using std :: min;
    int n,m;
    bool s[201][201],v[201];
    void floyd() {
    for (int k = 1;k <= n;k++)
    for (int i = 1;i <= n;i++)
    for (int j = 1;j <= n;j++)
    if (s[i][k] && s[k][j]) s[i][j] = true;
    }
    int main() {
    memset(s,false,sizeof(s));
    scanf("%d",&n);
    int x;
    for (int i = 1;i <= n;i++)
    while (scanf("%d",&x),x != 0)
    s[i][x] = true;
    floyd();
    int ans = 0;
    memset(v,true,sizeof(v));
    for (int i = 1;i <= n;i++)
    if (v[i]) {
    for (int j = 1;j <= n;j++)
    if (j != i && s[i][j] && s[j][i])
    v[j] = false;
    ans++;
    v[i] = false;
    }
    printf('%d',ans);
    return 0;
    }

  • 0
    @ 2018-06-29 15:58:18

    自学python的第一天...写了好久
    ```python 3
    global Darr;
    n=input();
    n=int(n);
    Father=[(i+1) for i in range(n)];
    Darr=[[0 for i in range(n)] for j in range(n)]
    Friends=[[False for i in range(n)] for j in range(n)];
    for i in range(n):
    num=input().split(' ');
    Darr[i]=list(map(int,num));

    global ArrStack,TopStack,ArrExistStack;
    global TimeCnt;
    global Ans;
    global vis;
    global Dfn,Low;
    TimeCnt=0;
    vis=[False for i in range(n)];
    Low=[0 for i in range(n)];
    Dfn=[0 for i in range(n)];
    ArrStack=[0 for i in range(n)];
    ArrExistStack=[0 for i in range(n)];
    Ans=0;
    TopStack=-1;
    def Tarjan(u):
    global Darr;
    global TimeCnt;
    global Ans;
    global vis;
    global Dfn,Low;
    global ArrStack, TopStack, ArrExistStack;
    vis[u-1]=True;
    TimeCnt+=1;
    Dfn[u-1]=Low[u-1]=TimeCnt;
    TopStack+=1;
    ArrStack[TopStack]=u;
    ArrExistStack[u-1]=2;
    for j in range(len(Darr[u-1])):
    v=Darr[u-1][j];
    if v==0:
    break;
    if not vis[v-1]:
    Tarjan(v);
    Low[u - 1] = min(Low[u - 1], Low[v - 1]);
    elif ArrExistStack[v-1]==2:
    Low[u-1]=min(Low[u-1],Low[v-1]);
    if Dfn[u-1]==Low[u-1]:
    Ans+=1;
    while TopStack>=0:
    ArrExistStack[ArrStack[TopStack]-1]=1;
    TopStack-=1;
    if ArrStack[TopStack+1]==u:
    break;
    for i in range(n):
    if not vis[i]:
    Tarjan(i+1);
    print(Ans);
    ```

  • 0
    @ 2016-11-19 18:40:34

    我用的是tarjan算法。。。求强联通分量的数目,一开始也想到并查集了,但不想写。
    测试数据 #0: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 856 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 856 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 852 KiB, score = 10
    Accepted, time = 0 ms, mem = 856 KiB, score = 100
    代码:
    var
    side:array[0..200,0..200] of boolean;
    stack,dfn,low:array[0..200] of longint;
    v:array[0..200] of boolean;
    deep,top,n,i,m,x,y,ans:longint;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a) else exit(b);
    end;
    procedure tarjan(x:longint);
    var
    i:longint;
    begin
    inc(deep);
    dfn[x]:=deep;low[x]:=deep;
    inc(top);
    stack[top]:=x;
    v[x]:=true;
    for i:=1 to n do
    if side[x,i] then begin
    if dfn[i]=0 then begin
    tarjan(i);
    low[x]:=min(low[x],low[i]);
    end
    else
    if v[i] then low[x]:=min(low[x],dfn[i]);
    end;
    if dfn[x]=low[x] then begin inc(ans);
    repeat
    v[stack[top]]:=false;
    dec(top);
    until stack[top+1]=x;
    end;
    end;

    begin
    fillchar(side,sizeof(side),false);
    readln(n);
    for i:=1 to n do
    begin
    read(x);
    while x<>0 do
    begin
    side[i,x]:=true;
    read(x);
    end;
    end;
    ans:=0;
    top:=0;
    deep:=0;
    for i:=1 to n do
    if dfn[i]=0 then tarjan(i);
    writeln(ans);
    end.

  • 0
    @ 2016-07-16 11:33:07

    GY解题报告
    //思路:裸的强连通分量
    //代码:Kosaraju
    using namespace std;
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<stack>
    #define maxn 200+10
    #define maxm 200*200+100

    int n,m,first[5][maxn],next[5][maxm],u[5][maxm],v[5][maxm],vis[maxn],ans;
    stack<int>s;
    struct f
    { int rank,father; }f[maxn];
    void merge(int u,int v);

    void dfs(int t,int flag)
    {
    int k=first[flag][t];
    while(k!=-1)
    {
    if(vis[v[flag][k]]==0)
    {
    if(flag==2)
    merge(u[flag][k],v[flag][k]);
    vis[v[flag][k]]=1;
    dfs(v[flag][k],flag);
    }
    k=next[flag][k];
    }
    if(flag==1)
    s.push(t);
    return;
    }

    int main()
    {
    freopen("P1022.in","r",stdin);

    cin>>n;
    memset(first[1],-1,sizeof(first[1]));m=0;
    for(int i=1;i<=n;i++)
    {
    int t;cin>>t;
    while(t!=0)
    {
    m++;
    u[1][m]=i,v[1][m]=t;
    next[1][m]=first[1][u[1][m]];first[1][u[1][m]]=m;
    cin>>t;
    }
    }

    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
    f[i].rank=1,f[i].father=i;
    if(vis[i]==0)
    {
    vis[i]=1;
    dfs(i,1);
    }
    }

    memset(first[2],-1,sizeof(first[2]));
    for(int i=1;i<=m;i++)
    {
    u[2][i]=v[1][i],v[2][i]=u[1][i];
    next[2][i]=first[2][u[2][i]];first[2][u[2][i]]=i;
    }

    memset(vis,0,sizeof(vis));
    while(!s.empty())
    {
    int t=s.top();
    if(vis[t]==0)
    {
    vis[t]=1;
    dfs(t,2);
    }
    s.pop();
    }

    ans=0;
    for(int i=1;i<=n;i++)
    if(f[i].father==i)
    ans++;
    cout<<ans<<endl;

    return 0;
    }

    int getf(int v)
    {
    if(f[v].father==v)
    return v;
    else
    {
    f[v].father=getf(f[v].father);
    return f[v].father;
    }
    }

    void merge(int u,int v)
    {
    int t1=getf(u);int t2=getf(v);
    if(t1!=t2)
    {
    if(f[t1].rank=f[t2].rank)
    {
    f[t2].father=t1;f[t1].rank+=f[t2].rank;
    }
    else
    {
    f[t1].father=t2;f[t2].rank+=f[t1].rank;
    }
    }
    }

  • 0
    @ 2016-03-13 11:14:09

    BFS
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 564 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    Accepted, time = 0 ms, mem = 564 KiB, score = 100

    代码
    #include<cstdio>
    #include<vector>
    using namespace std;

    template <typename T>
    class arrayQueue {
    public:
    arrayQueue(int initialCapacity = 10) {
    arrayLength = initialCapacity;
    Queue = new T [arrayLength];
    theFront = 0;
    theBack = 0;
    }
    ~arrayQueue() {
    delete [] Queue;
    }

    T& front() {
    return Queue[(theFront + 1) % arrayLength];
    }
    bool empty() {
    return theFront == theBack;
    }
    void pop() {
    theFront = (theFront + 1) % arrayLength;
    Queue[theFront].~T();
    }
    void push(const T &element) {
    theBack = (theBack + 1) % arrayLength;
    Queue[theBack] = element;
    }
    private:
    int theFront;
    int theBack;
    int arrayLength;
    T *Queue;
    };

    const int MaxN = 200 + 10;

    int N, M, K;
    bool visit[MaxN];

    vector <int> Graph[MaxN];
    arrayQueue<int> Q(MaxN);

    void BFS(const int &X) {
    Q.push(X); visit[X] = 1;
    while(!Q.empty()) {
    int Now = Q.front(); Q.pop(); visit[Now] = 1;
    for(vector<int>::iterator i = Graph[Now].begin(); i != Graph[Now].end(); ++i)
    if(!visit[*i]) Q.push(*i);
    }
    }

    int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i)
    while(scanf("%d", &K) == 1&& K)
    Graph[i].push_back(K);
    for(int i = 1; i <= N; ++i)
    if(!visit[i]) {
    ++M; BFS(i);
    }
    printf("%d", M);
    return 0;
    }

  • 0
    @ 2016-03-01 21:21:54

    Vijos数据这么水还能不能好好玩耍了。。。

  • 0
    @ 2015-10-27 21:40:20

    并查集过的。。。打开标签一看是图结构顿时就醉了。。。。
    上附代码

  • 0
    @ 2015-07-07 22:53:01

    P1022Victoria的舞会2
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1022 Victoria的舞会2
    递交时间 2015-07-07 22:52:22
    代码语言 C++
    评测机 VijosEx
    消耗时间 30 ms
    消耗内存 304 KiB
    评测时间 2015-07-07 22:52:24

    评测结果

    编译成功

    foo.cpp: In function 'void dfs(int)':
    foo.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( i = 0 ; i < l[x].after.size() ; i++ )
    ^

    测试数据 #0: Accepted, time = 0 ms, mem = 300 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 304 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 304 KiB, score = 10

    测试数据 #9: Accepted, time = 15 ms, mem = 300 KiB, score = 10

    Accepted, time = 30 ms, mem = 304 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <stack>

    using namespace std;

    int m;
    int n;
    int dfn[1000 + 10];
    int low[1000 + 10];
    int visit[1000 + 2];
    int cnt;
    stack < int > st;
    int i , j;

    struct link
    {
    vector < int > after;
    };

    link l[1000 + 10];
    bool instack[1000 + 10];
    int a , b;
    int ans;

    void dfs( int x )
    {
    visit[x] = 1;
    dfn[x] = low[x] = cnt++;
    st.push( x );
    instack[ x ] = 1;
    int i;
    for( i = 0 ; i < l[x].after.size() ; i++ )
    {
    if( !visit[ l[x].after[i] ] )
    {
    dfs( l[x].after[i] );
    low[x] = min( low[x] , low[ l[x].after[i] ] );
    }
    else if( instack[ l[x].after[i] ] )
    low[x] = min( low[x] , dfn[ l[x].after[i] ] );
    }
    int v;
    if( low[x] == dfn[x] )
    {
    do
    {
    v = st.top();
    instack[ v ] = 0;
    st.pop();
    }
    while( v != x );
    ans++;
    }
    }

    int main()
    {
    cnt = 1;
    scanf( "%d" , &n );
    for( i = 1 ; i <= n ; i++ )
    while( scanf( "%d" , &b ) != EOF )
    {
    if( !b )
    break;
    l[i].after.push_back( b );
    }
    for( i = 1 ; i <= n ; i++ )
    if( !visit[i] )
    dfs( i );
    cout << ans << endl;
    return 0;
    }
    就没有人用tarjan?

  • 0
    @ 2015-06-20 10:45:09

    下一题和这一题一样
    program p1022;
    var a:array[1..200,1..200] of boolean;
    b:array[1..200] of boolean;
    n,i,j,k:integer;
    c:boolean;
    begin
    readln(n);
    fillchar(a,sizeof(a),false);
    fillchar(b,sizeof(b),false);
    for i:=1 to n do
    begin
    read(j);
    while j<>0 do
    begin
    a[i,j]:=true;
    read(j);
    end;
    readln;
    end;
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do a[i,j]:=a[i,j] or (a[i,k] and a[k,j]);
    c:=false;
    k:=0;
    while not c do
    begin
    inc(k);
    for i:=1 to n do
    if not b[i] then break;
    b[i]:=true;
    for j:=1 to n do
    if a[i,j] then b[j]:=true;
    c:=true;
    for i:=1 to n do
    if not b[i] then
    begin
    c:=false;
    break;
    end;
    end;
    writeln(k);
    end.

  • 0
    @ 2015-02-28 21:47:07

    tarjan强连通 今天百度学了一下,表示第一遍wa70,查了好久没发现错误,后来发现N的范围不是20而是200表示当时电脑卡的屏幕有点……而且那个各位的0在下一行,__刚好卡的时候没有显示__……
    其实可以说是裸的tarjan了

  • 0
    @ 2014-11-24 13:55:27

    var n,sum,i,x,k,j:longint;bo:boolean;b:array[0..200,0..200]of boolean;
    a:array[0..200]of boolean;
    begin
    readln(n);fillchar(b,sizeof(b),false);sum:=0; fillchar(a,sizeof(a),true); for i:=1 to n do begin read(x); while(x<>0)do begin b[i,x]:=true;read(x);end; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do if i<>j then b[i,j]:=b[i,j]or(b[i,k]and b[k,j]); for i:=1 to n do if a[i] then begin for j:=1 to n do if(j<>i)and b[i,j]and b[j,i] then a[j]:=false; inc(sum);a[i]:=false; end; writeln(sum); end.

  • 0
    @ 2014-10-14 21:50:21

    AC100纪念!!
    强连通分量就可以了 顺带一提 这题和Victoria舞会3一样的代码

  • 0
    @ 2014-02-07 12:43:24

    我蒟蒻来了,昨天仔细思考了一下,其实没问题的。
    让众大神见笑了。

  • 0
    @ 2014-02-06 21:00:49

    #include<stdio.h>
    using namespace std;
    long f[201][201],map[201][201],num[201],now[201],cnt,i,j,k,n;
    void dfs(long k)
    {
    long go,i;
    for (i=1;i<=num[k];i++)
    {
    go=map[k][i];
    if (now[go]==0)
    {
    now[go]=cnt;
    dfs(go);
    }
    }
    }
    int main()
    {
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
    {
    while (true)
    {
    scanf("%ld",&k);
    if (k==0) break;
    f[i][k]=true;
    }
    }
    for (k=1;k<=n;k++)
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if ((i!=k)&&(i!=j)&&(j!=k))
    f[i][j]=f[i][j]||f[i][k]&&f[k][j];
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if ((i!=j)&&(f[i][j]!=f[j][i]))
    {
    f[i][j]=false;
    f[j][i]=false;
    }
    for (i=1;i<=n;i++)
    {
    for (j=1;j<=n;j++)
    if (f[i][j])
    {
    num[i]++;
    map[i][num[i]]=j;
    }
    now[i]=0;
    }
    cnt=0;
    for (i=1;i<=n;i++)
    if (now[i]==0)
    {
    cnt++;now[i]=cnt;
    dfs(i);
    }
    printf("%ld",cnt);
    }
    以上是我的AC代码,写得很传统。
    但是我仍有点疑问。
    如果A和B互相有好(已经染在一起),发现A与C也互相友好(在A的BFS中搜到了C)
    那么C就直接染色。
    但要不要判断B与C的关系了呢?我没有,但也过了。
    仔细看下面大牛的代码,都没判断。
    可能我哪里理解错了吧,望众大神指教。

    BY 蒟蒻JSB 绍兴一中万岁!

  • 0
    @ 2013-12-07 10:57:12

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    Accepted, time = 0 ms, mem = 824 KiB, score = 100

    代码

    program P1022;
    var n:integer;
    a:array[1..200,1..200] of integer;
    num:array[1..200] of integer;
    flag:array[1..200] of boolean;
    i,count:integer; m:integer;

    procedure arrange(x:integer);
    var i,j,target:integer;
    begin
    for i:=1 to num[x] do
    if flag[a[x,i]] then
    begin
    target:=a[x,i];
    for j:=1 to num[target] do
    if a[target,j]=x then
    begin
    dec(m);
    flag[x]:=false;
    arrange(target);
    break;
    end;
    end;
    flag[x]:=false;
    end;

    begin
    {assign(input,'P1022.in');
    reset(input);
    assign(output,'P1022.out');
    rewrite(output);}
    readln(n);
    for i:=1 to n do
    begin
    count:=1;
    read(a[i,count]);
    while a[i,count]<>0 do
    begin
    inc(count);
    read(a[i,count]);
    end;
    num[i]:=count-1;
    end;

    fillchar(flag,sizeof(flag),true);
    for i:=1 to n do
    if num[i]=0 then flag[i]:=false;

    m:=n;
    i:=1;
    repeat
    while not flag[i] do inc(i);
    if i<=n then arrange(i);
    until i>n;

    writeln(m);
    {close(input); close(output);}
    end.

  • 0
    @ 2013-10-25 20:55:52

    那些说并查集的,我想说说我的看法吧。并查集主要优势在于合并集合和查找集合比较快,而这题根本用不到这两个操作,因此我认为用并查集完全发挥不出优势啊。你用并查集之前不还是要一个一个的加入,而当你把所有节点都加入好了之后题目也做完了。所以这题直接bfs染色计算有几个连通分量就可以了。
    个人拙见,纯属扯淡。

  • 0
    @ 2013-02-11 19:25:33

    首先请允许我吐槽一下,P1022和P1023基本完全就是一样的题,这样做真的好嘛~~

    首先用一个二维布尔数组f[i,j]存储i是否喜欢与j对话。
    再用弗洛伊德n^3(弱数据就用弱办法吧。。)来吧那个传递性做出来,就是题中的那个活捉A\B\C三只基友。
    然后N^2扫描一下,若f[i,j]<>f[j,i]的话就把它俩都弄成fasle;
    最后DFS一下就可以了。。 每次递归栈清零的时候INC一下计数就AC了。

    附P代码:

    var f:array[0..500,0..500]of boolean;
    g:array[0..500]of boolean;
    n,m,i,j,k,l,h:longint;

    procedure dfs(a:longint);
    var i:longint;
    begin
    if(g[a])then begin
    inc(l);
    g[a]:=false;
    for i:=1 to n do if(f[a,i])then begin
    dfs(i);
    end;
    dec(l);
    if(l=0)then inc(h);
    end;
    end;

    begin
    h:=0;
    fillchar(f,sizeof(f),false);
    fillchar(g,sizeof(g),true);
    readln(n);
    for i:=1 to n do
    begin
    m:=1;
    while m<>0 do begin
    read(m);
    f[i,m]:=true;
    end;
    end;
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if(f[i,k])and(f[k,j])then f[i,j]:=true;
    for i:=1 to n do for j:=1 to n do
    if(f[i,j]=true)and(f[j,i]=false)then f[i,j]:=false;
    for i:=1 to n do
    begin
    l:=0;
    dfs(i);
    end;
    writeln(h);
    end.

  • 0
    @ 2012-10-24 21:56:24

    果断并查集,中间有一个路径压缩……

信息

ID
1022
难度
4
分类
图结构 点击显示
标签
递交数
4221
已通过
1937
通过率
46%
被复制
4
上传者