题目地址：POJ 2762 先缩点，然后判断拓扑网络每层的个数是否为1（我承认如果事先不知道这题需要拓扑排序我是想不出来这点的。。。）。因为假如有一层为2的话，那么从此之后这两个岔路的点就不可能从一点到另一点的。 代码如下：
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=1000+10; int head[MAXN], Ecnt, scc, top, indx; int low[MAXN], dfn[MAXN], belong[MAXN], stk[MAXN], instack[MAXN]; struct node { int u, v, next; }edge[7000]; void add(int u, int v) { edge[Ecnt].v=v; edge[Ecnt].next=head[u]; head[u]=Ecnt++; } void tarjan(int u) { low[u]=dfn[u]=++indx; instack[u]=1; stk[++top]=u; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ scc++; while(1){ int v=stk[top--]; belong[v]=scc; instack[v]=0; if(u==v) break; } } } void init() { memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); Ecnt=top=indx=scc=0; } int head1[MAXN], Ecnt1, deg[MAXN]; struct node1 { int u, v, next; }edge1[7000]; void add1(int u, int v) { edge1[Ecnt1].v=v; edge1[Ecnt1].next=head1[u]; head1[u]=Ecnt1++; } bool topo(int scc) { int i, u, tot, m=scc; while(m--){ tot=0; for(i=1;i<=scc;i++){ if(!deg[i]){ tot++; u=i; deg[i]--; } } if(tot>1) return false; for(i=head1[u];i!=-1;i=edge1[i].next){ deg[edge1[i].v]--; } } return true; } void init1() { memset(deg,0,sizeof(deg)); memset(head1,-1,sizeof(head1)); Ecnt1=0; } int main() { int n, m, i, j, u, v, t, f; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); init(); while(m--){ scanf("%d%d",&u,&v); add(u,v); } for(i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } init1(); for(i=1;i<=n;i++){ for(j=head[i];j!=-1;j=edge[j].next){ v=edge[j].v; if(belong[i]!=belong[v]){ add1(belong[i],belong[v]); deg[belong[v]]++; //printf("%d %d\n",belong[i],belong[v]); } } } if(topo(scc)) puts("Yes"); else puts("No"); } return 0; }
