网站百度文库,建设厅报名网站,什么是电商平台推广,wifi和卫星有关系吗题意#xff1a;一个有向图#xff0c;无自环#xff0c;无重边#xff0c;让你判断这个图内的任意两点是否有路#xff1b; 解题思路#xff1a;首先#xff0c;判断两个点是否可达一般用出入度来判断#xff0c;如果在拓扑排序中同时有两个及以上入度同时为零的点一个有向图无自环无重边让你判断这个图内的任意两点是否有路 解题思路首先判断两个点是否可达一般用出入度来判断如果在拓扑排序中同时有两个及以上入度同时为零的点那么这些入度的为零的点肯定不可达因为没有路径指向它然后就是简化图了一个环的点肯定可达所以缩下点再拓扑排序下 代码 #includeiostream
#includealgorithm
#includevector
#includequeue
#includecstdio
#includecstring
#define maxn 10005
using namespace std;
struct Edge
{int to;int next;
}edge[maxn];
struct node
{int x;int y;
}a[maxn];
int low[maxn];
int dfn[maxn];
int instack[maxn];
int visit[maxn];
int sccno[maxn];
int cnt;
int step;
int index;
int scc_cnt;
int head[maxn];
int indeg[maxn];
int indegree[maxn];
vectorintscc[maxn];
void add(int u,int v)
{edge[cnt].nexthead[u];edge[cnt].tov;head[u]cnt;
}
void tarjan(int u)
{low[u]dfn[u]step;instack[index]u;visit[u]1;for(int ihead[u];i!-1;iedge[i].next){if(!dfn[edge[i].to]){tarjan(edge[i].to);low[u]min(low[u],low[edge[i].to]);}else if(visit[edge[i].to]){low[u]min(low[u],dfn[edge[i].to]);}}if(low[u]dfn[u]){scc_cnt;scc[scc_cnt].clear();do{scc[scc_cnt].push_back(instack[index]);sccno[instack[index]]scc_cnt;visit[instack[index]]0;index--;}while(u!instack[index1]);}return;
}
void init()
{memset(head,-1,sizeof(head));cntstepindex0;scc_cnt0;memset(visit,0,sizeof(visit));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(indegree,0,sizeof(indegree));
}
int topusort()
{int flag0;queueintq;while(!q.empty())q.pop();for(int i1;iscc_cnt;i){indeg[i]indegree[i];if(indeg[i]0)q.push(i);}while(!q.empty()){if(q.size()2)flag1;int tempq.front();q.pop();for(int j0;jscc[temp].size();j){for(int ihead[scc[temp][j]];i!-1;iedge[i].next){if(sccno[edge[i].to]!temp){indeg[sccno[edge[i].to]]--;if(indeg[sccno[edge[i].to]]0)q.push(sccno[edge[i].to]);}}}}return flag;
}
int main()
{int n,m;int x,y;int t;scanf(%d,t);while(t--){init();scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,a[i].x,a[i].y);add(a[i].x,a[i].y);}for(int i1;in;i)if(!dfn[i])tarjan(i);for(int i1;im;i)if(sccno[a[i].x]!sccno[a[i].y])indegree[sccno[a[i].y]];int anstopusort();if(ans1)printf(Light my fire!\n);elseprintf(I love you my love and our love save us!\n);}
}转载于:https://www.cnblogs.com/huangdao/p/8620088.html
