不裸缩点》。。。POJ2186受欢迎的牛
:first-child { margin-top: 0; } blockquote > :last-child { margin-bottom: 0; } img { border: 0; max-width: 100%; height: auto !important; margin: 2px 0; } table { border-collapse: collapse; border: 1px solid #bbbbbb; } td, th { padding: 4px 8px; border-collapse: collapse; border: 1px solid #bbbbbb; } @media only screen and (-webkit-max-device-width: 1024px), only screen and (-o-max-device-width: 1024px), only screen and (max-device-width: 1024px), only screen and (-webkit-min-device-pixel-ratio: 3), only screen and (-o-min-device-pixel-ratio: 3), only screen and (min-device-pixel-ratio: 3) { html, body { font-size: 17px; } body { line-height: 1.7; padding: 0.75rem 0.9375rem; color: #353c47; } h1 { font-size: 2.125rem; } h2 { font-size: 1.875rem; } h3 { font-size: 1.625rem; } h4 { font-size: 1.375rem; } h5 { font-size: 1.125rem; } h6 { color: inherit; } ul, ol { padding-left: 2.5rem; } blockquote { padding: 0 0.9375rem; } }
-->
div{font-size:15px;}.wiz-table-tools .wiz-table-menu-item.active .wiz-table-menu-sub {display: block}.wiz-table-tools .wiz-table-menu-sub:before, .wiz-table-tools .wiz-table-menu-sub:after {position: absolute;content: " ";border-style: solid;border-color: transparent;border-bottom-color: #cccccc;left: 22px;margin-left: -14px;top: -8px;border-width: 0 8px 8px 8px;z-index:10;}.wiz-table-tools .wiz-table-menu-sub:after {border-bottom-color: #ffffff;top: -7px;}.wiz-table-tools .wiz-table-menu-sub-item {padding: 4px 12px;font-size: 14px;}.wiz-table-tools .wiz-table-menu-sub-item.split {border-top: 1px solid #E0E0E0;}.wiz-table-tools .wiz-table-menu-sub-item:hover {background-color: #ececec;}.wiz-table-tools .wiz-table-menu-sub-item.disabled {color: #bbbbbb;cursor: default;}.wiz-table-tools .wiz-table-menu-sub-item.disabled:hover {background-color: transparent;}.wiz-table-tools .wiz-table-menu-item.wiz-table-cell-bg:hover .wiz-table-color-pad {display: block;}.wiz-table-tools .wiz-table-color-pad {display: none;padding: 10px;box-sizing: border-box;width: 85px;height: 88px;background-color: #fff;cursor: default;}.wiz-table-tools .wiz-table-color-pad > div{font-size:15px;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item {display: inline-block;width: 15px;height: 15px;margin-right: 9px;position: relative;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item i.pad-demo {position: absolute;top:3px;left:0;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item .icon-oblique_line{color: #cc0000;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item:last-child {margin-right: 0;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item.active i.editor-icon.icon-box {color: #448aff;}.wiz-table-tools .wiz-table-cell-align {display: none;padding: 10px;box-sizing: border-box;width: 85px;height: 65px;background-color: #fff;cursor: default;}.wiz-table-tools .wiz-table-cell-align .wiz-table-cell-align-item {display: inline-block;width: 15px;height: 15px;margin-right: 9px;position: relative;}.wiz-table-tools .wiz-table-cell-align .wiz-table-cell-align-item:last-child {margin-right:0}.wiz-table-tools .wiz-table-cell-align .wiz-table-cell-align-item i.valign{position: absolute;top:3px;left:0;color: #d2d2d2;}.wiz-table-tools .wiz-table-cell-align-item.active i.editor-icon.valign {color: #a1c4ff;}.wiz-table-tools .wiz-table-cell-align-item.active i.editor-icon.icon-box,.wiz-table-tools .wiz-table-cell-align-item.active i.editor-icon.align {color: #448aff;}.wiz-table-tools .wiz-table-color-pad .wiz-table-color-pad-item:last-child,.wiz-table-tools .wiz-table-cell-align .wiz-table-cell-align-item:last-child {margin-right: 0;}th.wiz-selected-cell-multi, td.wiz-selected-cell-multi {background: rgba(0,102,255,.05);}th:before,td:before,#wiz-table-col-line:before,#wiz-table-range-border_start_right:before,#wiz-table-range-border_range_right:before{content: " ";position: absolute;top: 0;bottom: 0;right: -5px;width: 9px;cursor: col-resize;background: transparent;z-index:100;}th:after,td:after,#wiz-table-row-line:before,#wiz-table-range-border_start_bottom:before,#wiz-table-range-border_range_bottom:before{content: " ";position: absolute;left: 0;right: 0;bottom: -5px;height: 9px;cursor: row-resize;background: transparent;z-index:100;}.wiz-table-container {}.wiz-table-body {position:relative;padding:0 0 10px;overflow-x:auto;overflow-y:hidden;-webkit-overflow-scrolling:touch;}.wiz-table-body table {margin:0;outline:none;}td,th {height:28px;word-break:break-all;box-sizing:border-box;outline:none;}body pre.prettyprint {padding:0;}body pre.prettyprint code {white-space: pre;}body pre.prettyprint.linenums {box-shadow:none; overflow: auto;-webkit-overflow-scrolling: touch;}body pre.prettyprint.linenums ol.linenums {box-shadow: 40px 0 0 #FBFBFC inset, 41px 0 0 #ECECF0 inset; padding: 10px 10px 10px 40px !important;}
-->
1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4930 Solved: 2626
[Submit][Status][Discuss]
Description
Input
Output
一个数，即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
1 2
2 1
2 3
Sample Output
HINT
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define N 10002
vector<int>Gra[N];
stack<int>Sta;
int low[N],dfn[N],inStack[N],belong[N],sum[N],outDegree[N],Time,cnt;
void Tarjan(int s)
{ dfn[s] = low[s] = ++Time;
Sta.push(s); inStack[s] = 1;
for(int i=0;i<Gra[s].size();i++)
{
int j = Gra[s][i];
if(dfn[j] == 0){
Tarjan(j);
low[s] = min(low[s], low[j]);
}
else if(inStack[j]){
low[s] = min(low[s], dfn[j]);
}
}
if(dfn[s] == low[s])
{
cnt++;
while(!Sta.empty()){
int k = Sta.top(); Sta.pop();
sum[cnt] ++;
belong[k] = cnt;
inStack[s] = 0;
if(k == s) break;
}
}
return ;
}int main()
{ int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
Gra[x].push_back(y);
}
Time = cnt = 0;
memset(sum,0,sizeof(sum));
memset(inStack,0,sizeof(inStack));
memset(outDegree,0,sizeof(outDegree));
for(int i=1;i<=n;i++) if(dfn[i] == 0) Tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=0;j<Gra[i].size();j++){
int k = Gra[i][j];
if(belong[i] != belong[k]){
outDegree[belong[i]]++;
}
}
}
int outDegree_0 = 0;
int ret ;
for(int i=1;i<=cnt;i++)
{
if(outDegree[i] == 0){
outDegree_0 ++;
ret = sum[i];
}
}
if(outDegree_0 > 1) printf("0");
else printf("%d",ret);
} |