无锡建设机械网站制作,做个app需要多少费用,网络技术有限公司是什么,wordpress 优化配置1 /*2 题目大意#xff1a;有N个cows, M个关系3 a-b 表示 a认为b popular#xff1b;如果还有b-c, 那么就会有a-c 4 问最终有多少个cows被其他所有cows认为是popular#xff01;5 6 思路#xff1a;强连通分量中每两个节点都是可达的#xff… 1 /*2 题目大意有N个cows, M个关系3 a-b 表示 a认为b popular如果还有b-c, 那么就会有a-c 4 问最终有多少个cows被其他所有cows认为是popular5 6 思路强连通分量中每两个节点都是可达的 通过分解得到最后一个连通分量A7 如果将所有的强连通分量看成一个大的节点那么A一定是孩子节点因为我们先8 完成的是父亲节点的强连通分量! 最后如果其他的强连通分量都可以指向A那么9 A中的每一个cow都会被其他cows所有的cows认为popular
10 */
11 #include string
12 #include cstdio
13 #include cstring
14 #include iostream
15 #includevector
16 #define M 10005
17 using namespace std;
18
19 vectorintex[M];
20 vectorintey[M];
21
22 int n, m;
23 int cnt[M];//记录第一次dfs的节点的逆序
24 int vis[M];//标记节点是否已经被访问过了
25 int mark[M];//标记每一个节点是属于哪一个连通分量
26 int ans;
27 int top;
28
29 void dfs1(int u){//出度遍历
30 if(!vis[u]){
31 vis[u]1;
32 int lenex[u].size();
33 for(int i0; ilen; i){
34 int vex[u][i];
35 dfs1(v);
36 }
37 cnt[top]u;
38 }
39 }
40
41 void dfs2(int u){//入度遍历
42 if(!vis[u]){
43 vis[u]1;
44 mark[u]ans;
45 int leney[u].size();
46 for(int i0; ilen; i){
47 int vey[u][i];
48 dfs2(v);
49 }
50 }
51 }
52
53 int main(){
54 while(scanf(%d%d, n, m)!EOF){
55 while(m--){
56 int u, v;
57 scanf(%d%d, u, v);
58 ex[u].push_back(v);
59 ey[v].push_back(u);
60 }
61 anstop0;
62 for(int i1; in; i)
63 if(!vis[i])
64 dfs1(i);
65
66 memset(vis, 0, sizeof(vis));
67
68 for(int itop-1; i0; --i)
69 if(!vis[cnt[i]]){
70 ans;
71 dfs2(cnt[i]);
72 }
73 int count0;
74 int u0;
75 for(int i1; in; i)
76 if(mark[i]ans){
77 count;
78 ui;
79 }
80 memset(vis, 0, sizeof(vis));
81 dfs2(u);
82
83 for(int i1; in; i)//其他的强连通分量是否都指向了最后一个强连通分量
84 if(!vis[i]){
85 count0;
86 break;
87 }
88 printf(%d\n, count);
89 for(int i1; in; i){
90 ex[i].clear();
91 ey[i].clear();
92 }
93 memset(vis, 0, sizeof(vis));
94 }
95 return 0;
96 }1 /*2 tarjan 算法果然nb 首先我们利用该算法将所有的强连通分量分开3 然后将每一个连通分量看成是一个点这样就成了一个有向无环图4 接着判断初度为 0 的点一共有多少个如果只有一个那么最终的答案就是5 这个节点终所有子节点的个数也就是说这个节点中的每一个子节点都能 6 其他的所有节点到达7 8 如果初度为 0 的点多余1个那么对不起不能满足某个节点恰好能被其他所有9 的节点访问到!
10 */#includeiostream
11 #includecstdio
12 #includevector
13 #includestack
14 #includecstring
15 #define M 10005
16 using namespace std;
17
18 vectorintedge[M];
19 stackints;
20 int low[M], vis[M];
21 int sccN[M], pre[M];
22 int n, m;
23 int dfs_clock, cnt;
24
25 void dfs(int u){//tarjan 算法
26 int len edge[u].size();
27 pre[u]low[u]dfs_clock;
28 s.push(u);
29 for(int i0; ilen; i){
30 int vedge[u][i];
31 if(!pre[v]){
32 dfs(v);
33 low[u]min(low[u], low[v]);
34 }
35 else if(!sccN[v])
36 low[u] min(low[u], pre[v]);
37 }
38 if(low[u]pre[u]){
39 cnt;
40 while(1){
41 int vs.top();
42 s.pop();
43 sccN[v]cnt;
44 if(uv) break;
45 }
46 }
47 }
48
49 int main(){
50 while(scanf(%d%d, n, m)!EOF){
51 dfs_clockcnt0;
52 memset(pre, 0, sizeof(pre));
53 memset(sccN, 0, sizeof(sccN));
54 memset(vis, 0, sizeof(vis));
55 while(m--){
56 int u, v;
57 scanf(%d%d, u, v);
58 edge[u].push_back(v);
59 }
60 for(int i1; in; i)
61 if(!pre[i])
62 dfs(i);
63 int num0;
64 for(int i1; in; i)
65 if(sccN[i]1)
66 num;
67 int count0;
68 memset(vis, 0, sizeof(vis));
69 for(int i1; in; i){
70 int lenedge[i].size();
71 for(int j0; jlen; j)
72 if(sccN[i] ! sccN[edge[i][j]]){
73 vis[sccN[i]]1;
74 break;
75 }
76 }
77
78 for(int i1; icnt; i)
79 if(!vis[i]) count;
80 if(count1)
81 printf(%d\n, num);
82 else printf(0\n);
83 for(int i1; in; i)
84 edge[i].clear();
85 while(!s.empty())
86 s.pop();
87 }
88 return 0;
89 } 1 /*比较慢的方法就是利用tarjan算法将所有的强连通分量进行分离之后2 将每一个强连通分量看成是一个点如果有满足我们答案的解那么初度为零3 点一定只有一个并且这个点的所有子节点的编号是 1那么我们先计算出子节点4 编号为 1的个数 然后在判断其他的强连通分量的节点是否能够到达编号为 1 的5 强连通分量 */6 #includeiostream7 #includecstdio8 #includevector9 #includestack10 #includecstring11 #define M 1000512 using namespace std;13 14 vectorintedge[M];15 stackints;16 int low[M], vis[M], used[M];17 int sccN[M], pre[M];18 int n, m;19 int dfs_clock, cnt, sum, xx;20 21 void dfs(int u){22 int len edge[u].size();23 pre[u]low[u]dfs_clock;24 s.push(u);25 for(int i0; ilen; i){26 int vedge[u][i];27 if(!pre[v]){28 dfs(v);29 low[u]min(low[u], low[v]); 30 } 31 else if(!sccN[v])32 low[u] min(low[u], pre[v]); 33 } 34 if(low[u]pre[u]){35 cnt;36 while(1){37 int vs.top();38 s.pop();39 sccN[v]cnt;40 if(uv) break;41 } 42 }43 }44 45 int dfs2(int u){46 int lenedge[u].size();47 if(sccN[u]1){//到达之后就不在进行任何搜索 48 sumxx;49 return 1; 50 }51 vis[u]1;52 for(int i0; ilen; i){53 int vedge[u][i];54 if(!vis[v]){55 if(dfs2(v))56 return 1; 57 }58 } 59 return 0;60 }61 62 int main(){63 while(scanf(%d%d, n, m)!EOF){64 dfs_clockcnt0;65 memset(pre, 0, sizeof(pre));66 memset(sccN, 0, sizeof(sccN));67 memset(vis, 0, sizeof(vis));68 memset(used, 0, sizeof(used));69 while(m--){70 int u, v;71 scanf(%d%d, u, v);72 edge[u].push_back(v); 73 } 74 for(int i1; in; i)75 if(!pre[i]) 76 dfs(i);77 int num0; 78 sum0;79 used[1]1;80 for(int i1; in; i){81 82 if(sccN[i]1)83 num;84 else if(!used[sccN[i]]){85 memset(vis, 0, sizeof(vis));86 xxsccN[i];87 used[sccN[i]]1; 88 dfs2(i);89 }90 }91 92 if(sum(cnt1)*cnt/2-1)//最后将能到达标号为1的连通分量的所有强连通分量的标号加起来 93 printf(%d\n, num);94 else printf(0\n);95 for(int i1; in; i)96 edge[i].clear();97 while(!s.empty())98 s.pop();99 }
100 return 0;
101 } 转载于:https://www.cnblogs.com/hujunzheng/p/3895221.html
