EZOJ #257

传送门

分析

先进行缩点

之后从终点倒着跑

对于一组边如果有一个点不能到达则这组边直接废掉

最后看只用没废掉的边能不能从起点走到终点

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int n,m,vis[],gone[],a[],t;

int sum,cnt,ist[],belong[],low[],dfn[];

stack<int>A;

vector<int>b[],v[],nv[],vv[];

inline void tarjan(int x){

    dfn[x]=low[x]=++cnt;

    ist[x]=;

    A.push(x);

    for(int i=;i<v[x].size();i++)

      if(!dfn[v[x][i]]){

          tarjan(v[x][i]);

          low[x]=min(low[x],low[v[x][i]]);

      }else if(ist[v[x][i]]){

          low[x]=min(low[x],dfn[v[x][i]]);

      }

    if(low[x]==dfn[x]){

      sum++;

      while(){

          int u=A.top();

          A.pop();

          ist[u]=;

          belong[u]=sum;

          if(u==x)break;

      }

    }

}

inline void dfs(int x){

    if(vis[x])return;

    vis[x]=;

    for(int i=;i<vv[x].size();i++)dfs(vv[x][i]);

}

inline void pr(){puts("YES");exit();}

inline void go(int x){

    if(gone[x])return;

    if(x==belong[t])pr();

    gone[x]=;

    for(int i=;i<nv[x].size();i++)go(nv[x][i]);

}

int main(){

    int i,j,k;

    scanf("%d%d",&n,&m);

    t=n+;

    for(i=;i<=m;i++){

      scanf("%d%d",&a[i],&k);

      for(j=;j<=k;j++){

          int x;

          scanf("%d",&x);

          b[i].push_back(x);

          v[a[i]].push_back(x);

      }

      if(!k)v[a[i]].push_back(t);

    }

    for(i=;i<=n;i++)

      if(!dfn[i])tarjan(i);

    for(i=;i<=n;i++)

      for(j=;j<v[i].size();j++)

        if(belong[i]!=belong[v[i][j]])

          vv[belong[v[i][j]]].push_back(belong[i]);

    dfs(belong[t]);

    for(i=;i<=m;i++){

      int ok=;

      for(j=;j<b[i].size();j++)

        if(!vis[belong[b[i][j]]]){

          ok=;

          break;

        }

      if(ok){

          for(j=;j<b[i].size();j++)

            nv[belong[a[i]]].push_back(belong[b[i][j]]);

          if(!b[i].size())nv[belong[a[i]]].push_back(belong[t]);

      }

    }

    go(belong[]);

    puts("NO");

    return ;

}