- Victoria的舞会2
- 2017-11-27 10:44:17 @
这里附我的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 条评论
目前还没有评论...