数据有错

这里附我的wa代码和通过代码:
通过代码:

#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;
}

我的代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
struct node{
    int to,next;
};
node edge[maxn*maxn];
int n, head[maxn],cnt, scc_num,vis[maxn],low[maxn],dfn[maxn];
stack<int>s;

void tardfs(int pos,int k){
    low[pos]=dfn[pos]=k;
    vis[pos]=1;
    s.push(pos);
    for(int i=head[pos];i!=-1;i=edge[i].next){
        int to=edge[i].to;
        if(vis[to]==0)tardfs(to,k+1);
        if(vis[to]==1)low[pos]=min(low[pos],low[to]);
    }
    if(low[pos]==dfn[pos]){
        scc_num++;
        while(1){
            int to=s.top();
            s.pop();
            vis[to]=-1;
            low[to]=scc_num;
            if(to==pos)break;
        }
    }
}

void tarjian(){
    memset(vis,0,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    while(!s.empty())s.pop();
    for(int i=1;i<=n;i++){
        if(vis[i]==0)tardfs(i,1);

    }
}

void add(int s,int e){
    edge[cnt].to=e;
    edge[cnt].next=head[s];
    head[s]=cnt++;
}

int main(){
    while(~scanf("%d",&n)){
        memset(head,-1,sizeof(head));
        cnt=0;
        scc_num=0;
        for(int i=1;i<=n;i++){
            int to;
            while(scanf("%d",&to) && to){
                add(i,to);
            }
        }
        tarjian();
        cout<<scc_num<<endl;
    }
}


/*
8
2 7 0
1 3 5 0
4 0
2 0
6 0
2 0
8 0
1 0

*/

我的wa的代码拉到tyvj上面一下交

过了,来看这个在vijos上面ac的代码:
他用floyd来判断任意两点之间是否可达,但是这种判断是有问题的,如果1,5之间可达,5 4之间可达,4 3之间可达,3 2之间可达,2 1之间可达,那么在他的判断中,由于先输入的是1能到达5的原因,它无法判断出1 3之间是可达的,其他情况类似,然后在下面那种取巧的判断自然也就错了

0 条评论

目前还没有评论...

信息

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