就是先tarjan+缩点 （hh神的模板）
然后新图必须满足：
1.入度为0的点只能有一个
2.出度为0的点只能有一个
入度在构建新图时顺便开个数组记录一下就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxm = 10000;

vector <int> edge[maxm];
vector <int> now[maxm];
int hash[maxm];
bool vis[maxm];
int dfn[maxm],Index;
int low[maxm];
int idx[maxm];
int ss[maxm],top;
bool InStack[maxm];
bool ruInNew[maxm];
int n;
int nn;

void dfs(int u)
{
    vis[u] = true;
    dfn[u] = low[u] = Index++;
    InStack[u] = true;
    ss[++top] = u;
    for(int i=0;i<edge[u].size();i++)
    {
        int v = edge[u][i];
        if(!vis[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(InStack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        int v = -1;
        nn++;
        while(u != v)
        {
            v = ss[top--];
            InStack[v] = false;
            idx[v] = nn;
        }
    }
}

void tarjan()
{
    int i;
    for(i=0;i<maxm;i++) now[i].clear();
    memset(vis,0,sizeof(vis));
    memset(ruInNew,0,sizeof(ruInNew));
    Index = 1;
    top = 0;
    nn = 0;
    for(i=1;i<=n;i++){
        if(!vis[i]) dfs(i);
    }
    memset(hash,-1,sizeof(hash));
    for(i=1;i<=n;i++)
        for(int j=0;j<edge[i].size();j++)
        {
            int v = edge[i][j];
            if(idx[i] != idx[v] && hash[idx[i]] != idx[v])
            {
                hash[idx[i]] != idx[v];
                now[idx[i]].push_back(idx[v]);
                ruInNew[v] = true;
            }
        }
}

int ok()
{
    int i;
    int ru=0, chu=0;
    for(i=1;i<=nn;i++)
    {
        if(ruInNew[i] == false) ru++;
        if(now[i].size() == 0) chu++;
    }
    if(ru==1 && chu==1) return 1;
    return 0;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int T,i,m;
    scanf("%d",&T);
    while(T--)
    {
        for(i=0;i<maxm;i++) edge[i].clear();
        scanf("%d%d",&n,&m);
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
        }
        tarjan();
        if(ok()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

• Re:目前我还没发现不拓扑排序有啥不对的。。完全可以啊 (0) ssdut_201392326 2014-08-12 16:16:21
• Re:这道题大家写麻烦了！ tarjan+缩点就做完了啊~拓扑排序干嘛 0_0【329ms】 (26) qpswwww 2014-08-14 20:24:30
• 给组数据，就知道为什么了 (134) XKing 2015-05-06 10:36:47
• 你这很明显错了啊 (75) sd197555 2016-11-01 11:16:19
  • Re:你这很明显错了啊 (101) hzoi2017ybc 2018-05-18 16:02:30
    • Re:你这很明显错了啊 (56) hzoi2017ybc 2018-05-18 16:04:16