tarjan

tarjan缩点的运用，寻找一个较小的点集使得从这些点出发能够到达任意不在点集中的点，若有多个点，输出这些集合升序排序后字典序最小的

可达性
思路：先进行缩点，再寻找出入度为0的强连通分量
du数组记录的是每个强连通分量的入度
cnt数组记录的是每个强连通分量中的最小点
sig记录的是强连通分量的个数

#include<bits/stdc++.h>
#define M 100100
using namespace std;
int low[M],dfn[M],tot,sig,temp;
stack<int> s;
int col[M],dep[M],n,m;
int du[M],cnt[M];
int ans[M],vis[M];
vector<int>vep[M];
void init( )
{
      tot=sig=temp=0;
      memset(vis,0,sizeof(vis));
      memset(low,0,sizeof(low));
      memset(col,0,sizeof(col));
      memset(dfn,0,sizeof(dfn));
      memset(dep,0,sizeof(dep));
      memset(du,0,sizeof(du));
      memset(cnt,M,sizeof(cnt));
      memset(ans,0,sizeof(ans));
      for(int i=0;i<M;i++)
      {
            vep[i].clear( );
      }
}
void tarjan(int x)
{
      dfn[x]=low[x]=++tot;
      s.push(x);
      vis[x]=1;
      for(int i=0;i<vep[x].size( );i++)
      {
            int j=vep[x][i];
            if(!dfn[j])
            {
                  tarjan(j);
                  low[x]=min(low[x],low[j]);
            }
            else if(vis[j])
            {
                  low[x]=min(low[x],dfn[j]);
            }
      }
      if(low[x]==dfn[x])
      {
            sig++;
            int k;
            do
            {
                  k=s.top( );
                  col[k]=sig;
                  vis[k]=0;
                  s.pop( );
            }while(x!=k);
      }
      return ;
}
void solve(int n)
{
      for(int i=1;i<=n;i++)
      {
            if(!dfn[i])
            {
                  tarjan(i);
            }
      }
      for(int i=1;i<=n;i++)
      {
            cnt[col[i]]=min(cnt[col[i]],i);
            for(int j=0;j<vep[i].size( );j++)
            {
                  int v=vep[i][j];
                  if(col[v]!=col[i])
                  {
                        du[col[v]]++;
                  }
            }
      }
      for(int i=1;i<=sig;i++)
      {
            if(du[i]==0)
            {
                  temp++;
                  ans[temp]=cnt[i];
            }
      }
      cout<<temp<<endl;
      sort(ans+1,ans+1+temp);
      for(int i=1;i<=temp;i++)
      {
            cout<<ans[i]<<" ";
      }
      cout<<endl;
      return ;
}
int main( )
{
      int x,y;
      cin>>n>>m;
      init();
      for(int i=1;i<=m;i++)
      {
            cin>>x>>y;
            vep[x].push_back(y);
      }
      solve(n);
      return 0;
}