{"id":152,"date":"2010-03-13T14:52:00","date_gmt":"2010-03-13T06:52:00","guid":{"rendered":"http:\/\/localhost\/?p=152"},"modified":"2010-03-13T14:52:00","modified_gmt":"2010-03-13T06:52:00","slug":"haoi2007_popular_cattle","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=152","title":{"rendered":"[HAOI2007]\u53d7\u6b22\u8fce\u7684\u725b"},"content":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem<\/a>
\u989d\u3002\u3002\u8fd9\u662f\u5f88\u8001\u7684\u5f3a\u8054\u901a\u9898\u76ee\u4e86\u3002\u521a\u521a\u5f04\u61c2\u4e86Tarjan\u7b97\u6cd5\u3002\u3002\u5c31\u50cf\u5b9e\u8df5\u4e00\u4e0b\u3002\u3002\u7ed3\u679cWA\u4e86
\u5f88\u4e45\u3002\u3002\u6700\u540e\u53d1\u73b0\u539f\u6765\u662fStack\u641e\u9519\u4e86\u3002\u3002\u771f\u662f\u60b2\u5267\u3002\u3002
\u5c31\u662f\u6c42\u51fa\u6bcf\u4e2a\u5f3a\u8054\u901a\u5206\u91cf\uff0c\u7136\u540e\u5982\u679c\u5165\u5ea6\u4e3a0\u7684\u5206\u91cf\u53ea\u6709\u4e00\u4e2a\uff0c\u7b54\u6848\u5c31\u662f\u8fd9\u4e2a\u5206\u91cf\u7684\u5927\u5c0f\uff0c\u5426\u5219\u5c31\u662f0
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
vector<int> E[maxn];
typedef vector<int>::iterator it;
int ord[maxn],low[maxn],cnt=0,id[maxn],snt=0,n,m;
bool inStack[maxn]={0};
stack<int> Stack;
void dfs(int x)
{
ord[x]=low[x]=cnt++;
inStack[x]=true;Stack.push(x);
for(it i=E[x].begin();i!=E[x].end();++i)
{
if(ord[*i]==-1)
dfs(*i),low[x]=min(low[x],low[*i]);
else if(inStack[*i]) low[x]=min(low[x],ord[*i]);
}
if(ord[x]==low[x])
{
int u;do{u=Stack.top();Stack.pop();id[u]=snt;inStack[u]=false;}while(u!=x);
snt++;
}
}
int Num[maxn]={0},In[maxn]={0};
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>m;int s,t;
while(m–) scanf("%d %d",&s,&t),E[t-1].pb(s-1);
rep(i,n) ord[i]=-1;
rep(i,n)if(ord[i]==-1) dfs(i);
rep(i,n){
int own=id[i];for(it e=E[i].begin();e!=E[i].end();++e)if(id[*e]!=own) In[id[*e]]++;
Num[own]++;
}
t=0;int ans=0;rep(i,snt)if(In[i]==0) ++t,ans+=Num[i];
if(t>1)cout<<0<<endl;
else cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem\u989d\u3002\u3002\u8fd9\u662f\u5f88\u8001\u7684\u5f3a\u8054\u901a\u9898\u76ee\u4e86\u3002\u521a\u521a\u5f04\u61c2\u4e86Tarjan\u7b97\u6cd5\u3002\u3002\u5c31\u50cf\u5b9e\u8df5\u4e00\u4e0b\u3002\u3002\u7ed3\u679cWA\u4e86\u5f88\u4e45\u3002\u3002\u6700\u540e\u53d1\u73b0\u539f\u6765\u662fStack\u641e\u9519\u4e86\u3002\u3002\u771f\u662f\u60b2\u5267\u3002\u3002\u5c31\u662f\u6c42\u51fa\u6bcf\u4e2a\u5f3a\u8054\u901a\u5206\u91cf\uff0c\u7136\u540e\u5982\u679c\u5165\u5ea6\u4e3a0\u7684\u5206\u91cf\u53ea\u6709\u4e00\u4e2a\uff0c\u7b54\u6848\u5c31\u662f\u8fd9\u4e2a\u5206\u91cf\u7684\u5927\u5c0f\uff0c\u5426\u5219\u5c31\u662f0Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<vector>#include<stack>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=10000;vector<int> E[maxn];typedef vector<int>::iterator it;int ord[maxn],low[maxn],cnt=0,id[maxn],snt=0,n,m;bool inStack[maxn]={0};stack<int> Stack;void dfs(int x){ ord[x]=low[x]=cnt++; inStack[x]=true;Stack.push(x); for(it i=E[x].begin();i!=E[x].end();++i) { if(ord[*i]==-1) dfs(*i),low[x]=min(low[x],low[*i]); else if(inStack[*i]) low[x]=min(low[x],ord[*i]); } if(ord[x]==low[x]) { int u;do{u=Stack.top();Stack.pop();id[u]=snt;inStack[u]=false;}while(u!=x); snt++; }}int Num[maxn]={0},In[maxn]={0};int main(){ \/\/freopen("in","r",stdin); cin>>n>>m;int s,t; while(m–) scanf("%d %d",&s,&t),E[t-1].pb(s-1); rep(i,n) ord[i]=-1; rep(i,n)if(ord[i]==-1) dfs(i); rep(i,n){ int own=id[i];for(it e=E[i].begin();e!=E[i].end();++e)if(id[*e]!=own) In[id[*e]]++; Num[own]++; } t=0;int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/152"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=152"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/152\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=152"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=152"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=152"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}