考察:枚举+dfs or bfs
错误思路:
枚举每个点,求往下能到达的点和往上能到达的点,用st数组标记去过的点,set收集当前枚举点i能到达的点.
此思路错在如果存在双向边,有的点能去的点还未更新完就用来更新其他点.这使得这些点获得的点是不完全的,使得答案偏小.
正确思路:
枚举每个点,求往下能到达的点和往上能到达的点,每次枚举都清空st数组.st标记去过的点.正向和反向的点集合为n,ans++
这题可以看出:链式向前星只与h数组有关,因此建立双向边不需要再开一个road数组.
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 const int N = 10010,M = 1010; 5 int n,m,idx,h[M],rh[M],ans; 6 bool st1[M],st2[M]; 7 struct Road{ 8 int fr,to,ne; 9 }road[N<<1]; 10 void add(int a,int b,int h[]) 11 { 12 road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 13 } 14 void dfs(int u,int h[],bool st[]) 15 { 16 st[u] =1; 17 for(int i=h[u];i!=-1;i=road[i].ne) 18 { 19 int v = road[i].to; 20 if(!st[v]) dfs(v,h,st); 21 } 22 } 23 int main() 24 { 25 scanf("%d%d",&n,&m); 26 memset(h,-1,sizeof h); 27 memset(rh,-1,sizeof rh); 28 while(m--) 29 { 30 int a,b; scanf("%d%d",&a,&b); 31 add(a,b,h); 32 add(b,a,rh); 33 } 34 int ans = 0; 35 for(int i=1;i<=n;i++) 36 { 37 memset(st1,0,sizeof st1); 38 memset(st2,0,sizeof st2); 39 dfs(i,h,st1); 40 dfs(i,rh,st2); 41 int cnt = 0; 42 for(int j=1;j<=n;j++) 43 if(st1[j]||st2[j]) cnt++; 44 if(cnt==n) ans++; 45 } 46 printf("%d\n",ans); 47 return 0; 48 }