首页 > 代码库 > bzoj1051题解
bzoj1051题解
【题意分析】
给你一张有向图，求有多少个点，满足以其他任意一点为起点都能到达该点。
【解题思路】
如果这张有向图不连通，则一定没有点能被其他所有点到达，答案为0。
然后先用tarjan缩一波强连通分量，因为每个强连通分量中任意两点能相互到达，所以整体可以看成一个点。
因为已经保证图的连通性，所以只要统计没有入度的强连通分量的点数和即可。复杂度O(n+m)。
【参考代码】
1 #include <cctype> 2 #include <cstdio> 3 #define REP(I,start,end) for(int I=(start);I<=(end);I++) 4 #define PER(I,start,end) for(int I=(start);I>=(end);I--) 5 typedef long long LL; 6 inline int getint() 7 { 8 char ch=getchar(); 9 for(;!isdigit(ch)&&ch!=‘-‘;ch=getchar()); 10 bool impositive=ch==‘-‘; 11 if(impositive) 12 ch=getchar(); 13 int result=0; 14 for(;isdigit(ch);ch=getchar()) 15 result=(result<<3)+(result<<1)+ch-‘0‘; 16 return impositive?-result:result; 17 } 18 inline LL getLL() 19 { 20 char ch=getchar(); 21 for(;!isdigit(ch)&&ch!=‘-‘;ch=getchar()); 22 bool impositive=ch==‘-‘; 23 if(impositive) 24 ch=getchar(); 25 LL result=0ll; 26 for(;isdigit(ch);ch=getchar()) 27 result=(result<<3)+(result<<1)+ch-‘0‘; 28 return impositive?-result:result; 29 } 30 template<typename T> inline bool getmax(T &target,T pattern) 31 { 32 return pattern>target?target=pattern,true:false; 33 } 34 template<typename T> inline bool getmin(T &target,T pattern) 35 { 36 return pattern<target?target=pattern,true:false; 37 } 38 //Header Template 39 #include <cstring> 40 #include <vector> 41 using namespace std; 42 bool instack[10010],visited[10010],ind[10010]; 43 int n,cardP,top,cnt,dfn[10010],low[10010],SCC[10010],Ssize[10010],stack[10010]; 44 vector<int> edge[10010],dedge[10010]; 45 inline bool BFS() 46 { 47 memset(visited,0,sizeof(visited)); 48 stack[1]=visited[1]=1; 49 for(int head=0,tail=1;head++<tail;) 50 { 51 int now=stack[head]; 52 for(int i=0;i<dedge[now].size();i++) 53 { 54 int p=dedge[now][i]; 55 if(!visited[p]) 56 { 57 stack[++tail]=p; 58 visited[p]=true; 59 } 60 } 61 } 62 bool result=true; 63 REP(i,1,n) 64 result&=visited[i]; 65 return result; 66 } 67 void Tarjan(int now) 68 { 69 dfn[now]=low[now]=++cardP; 70 stack[++top]=now; 71 instack[now]=visited[now]=true; 72 for(int i=0;i<edge[now].size();i++) 73 { 74 int p=edge[now][i]; 75 if(!visited[p]) 76 { 77 Tarjan(p); 78 getmin(low[now],low[p]); 79 } 80 else 81 if(instack[p]) 82 getmin(low[now],dfn[p]); 83 } 84 if(low[now]==dfn[now]) 85 { 86 Ssize[++cnt]=0; 87 while(top&&instack[now]) 88 { 89 int p=stack[top--]; 90 instack[p]=false; 91 SCC[p]=cnt; 92 Ssize[cnt]++; 93 } 94 } 95 } 96 int main() 97 { 98 n=getint(); 99 memset(edge,0,sizeof(edge));100 memset(dedge,0,sizeof(dedge));101 for(int m=getint();m--;)102 {103 int u=getint(),v=getint();104 edge[v].push_back(u);105 dedge[u].push_back(v);106 dedge[v].push_back(u);107 }108 if(!BFS())109 {110 putchar(‘0‘);111 putchar(‘\n‘);112 return 0;113 }114 cardP=top=cnt=0;115 memset(visited,0,sizeof(visited));116 memset(instack,0,sizeof(instack));117 REP(i,1,n)118 if(!visited[i])119 Tarjan(i);120 memset(ind,0,sizeof(ind));121 REP(i,1,n)122 for(int k=0;k<edge[i].size();k++)123 {124 int j=edge[i][k],scc=SCC[j];125 ind[scc]|=SCC[i]!=scc;126 }127 int ans=0;128 REP(i,1,cnt)129 ans+=(!ind[i])*Ssize[i];130 printf("%d\n",ans);131 return 0;132 }
bzoj1051题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。