http://poj.org/problem?id=2186
View Code
const int MM = 11111;
#define debug puts("wrong")
typedef __int64 int64;
int N,M;
vector<int>edge[MM];
const int maxn = 11111; //节点数
bool instack[maxn];
int ief,top,bcnt,st[maxn];
int low[maxn],dfn[maxn],belong[maxn];
int out[MM];
void get_data() {
int i,j,k,x,y;
for(i=0;i<=N;i++) edge[i].clear();
for(i=0;i<M;i++) {
scanf("%d%d",&x,&y);
edge[x].push_back(y);
}
}
void get_init(int n) { //节点数
for(int i=0;i<=n;i++)
low[i]=dfn[i]=instack[i]=belong[i]=0;
top=bcnt=0; ief=1;
}
void trajan(int u) {
int i,j,k,v;
dfn[u]=low[u]=ief++;
st[top++]=u; instack[u]=true;
for(i=0;i<edge[u].size();i++) {
v=edge[u][i];
if(!dfn[v]) trajan(v);
if(low[u]>low[v]) low[u]=low[v];
else if(instack[v] && dfn[v]<low[u]) low[u]=dfn[k];
}
if(low[u]==dfn[u]) {
bcnt++;
do {
v=st[--top];
instack[v]=false;
belong[v]=bcnt;
}while(u!=v);
}
}
int get_ans(int x) {
int res=0;
for(int i=1;i<=N;i++) if(belong[i]==x) res++;
return res;
}
void solve() {
int i,j,k,v;
get_init(N);
for(i=1;i<=N;i++) if(!dfn[i]) trajan(i);
for(i=1;i<=N;i++) out[i]=0;
for(i=1;i<=N;i++) {
for(j=0;j<edge[i].size();j++) {
v=edge[i][j];
if(belong[i]!=belong[v]) out[belong[i]]++;
}
}
int res,cc=0;
for(i=1;i<=bcnt;i++) if(!out[i]) cc++,res=i;
if(cc>1) puts("0");
else printf("%dn",get_ans(res));
}
原文链接: https://www.cnblogs.com/zhang1107/archive/2013/05/04/3058859.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/87112
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!