建设班级网站首页,网站与网络的区别,响应式网站404页面怎么做,软文推广方法//在一张有向无环图G#xff0c;图G会包含很多环#xff08;环里面的点是等价的#xff09;#xff0c;
//当然可以把环缩成一个点#xff08;利用tarjan缩点#xff09;#xff0c;
//形成一棵树#xff0c;题目要求是求除他以外的点都指向他#xff0c;也就是只有一… //在一张有向无环图G图G会包含很多环环里面的点是等价的
//当然可以把环缩成一个点利用tarjan缩点
//形成一棵树题目要求是求除他以外的点都指向他也就是只有一个叶子。
//因为一旦有两个那么两个叶子没有联系也就不满足除他以外所有点指向了。
//那么我们只要在缩点之后的图中找出出度为0的点然后输出它里面的点就可以了。 #includeiostream
#includecstdio
#includemath.h
#includequeue
#includemap
#includestdlib.h
#includestring
#includestring.h
#includealgorithm
using namespace std;
typedef long long LL;
#define PI acos(-1.0)
#define N 10020struct asd{int to;int next;
};
asd q[N*5];
int head[N*5];
int tol;
int n,m;int dfn[N];
int low[N];
int in[N];
int stap[N];
bool vis[N];
int tp,p;
int cnt;
int kr[N],kc[N];void tarjan(int u)
{dfn[u]low[u]tp;stap[p]u;vis[u]1;for(int ihead[u];i!-1;iq[i].next){int kq[i].to;if(!dfn[k]){tarjan(k);low[u]min(low[u],low[k]);}else if(vis[k]){low[u]min(low[u],dfn[k]);}}if(dfn[u]low[u]){int temp;cnt;while(1){tempstap[p];vis[temp]0;in[temp]cnt;--p;if(tempu)break;}}
}void add(int a,int b)
{q[tol].tob;q[tol].nexthead[a];head[a]tol;
}int main()
{while(~scanf(%d%d,n,m)){memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));tol0;memset(head,-1,sizeof(head));for(int i0;im;i){int a,b;scanf(%d%d,a,b);add(a,b);}cnttpp0;for(int i1;in;i){if(!dfn[i]){tarjan(i);}}memset(kr,0,sizeof(kr));for(int i1;in;i){for(int khead[i];k!-1;kq[k].next){int jq[k].to;if(in[j]!in[i]){kr[in[i]];}}}int sum0;int x;for(int i1;icnt;i){if(!kr[i]){sum;xi;}}if(sum1){int ans0;for(int i1;in;i){if(in[i]x)ans1;}printf(%d\n,ans);}else{puts(0);}}return 0;
} 转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934543.html
