2 条题解

  • 0
    @ 2025-10-8 16:49:55
    #include<bits/stdc++.h>
    using namespace std;
    const int N=5100;
    vector<int>G[N];
    int tsp,cnt,scc[N],low[N],dfn[N];
    stack<int>stk;bool instk[N];
    
    void tarjan(int x)
    {
        low[x]=dfn[x]=++tsp;
        stk.push(x);instk[x]=true;
        for(int y:G[x])
        {
            if(dfn[y]==0)
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(instk[y]==true)low[x]=min(low[x],dfn[y]);
    
        }
        if(low[x]==dfn[x])
        {
            cnt++;
            for(int z=-1;z!=x;)
            {
               z=stk.top();stk.pop();instk[z]=false;
               scc[z]=cnt;
            }
        }
    }
    
    int main()
    {
        int n,m;
        while(scanf("%d", &n)!=EOF&&n)
        {
            scanf("%d", &m);
            memset(G,0,sizeof(G));
            for(int i=1,x,y;i<=m;i++) {
                scanf("%d%d", &x, &y);
                G[x].push_back(y);
            }
        
            tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
            memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
            for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);
     
            vector<int>cd(cnt+1);
            for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j])cd[scc[i]]++;
            for(int i=1;i<=n;i++)if(cd[scc[i]]==0)printf("%d ", i);
            printf("\n");
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:49:32
      #include<bits/stdc++.h>
      using namespace std;
      const int N=5100;
      vector<int>G[N];
      int tsp,cnt,scc[N],low[N],dfn[N];
      stack<int>stk;bool instk[N];
      
      void tarjan(int x)
      {
          low[x]=dfn[x]=++tsp;
          stk.push(x);instk[x]=True;
          for(int y:G[x])
          {
              if(dfn[y]==0)
              {
                  tarjan(y);
                  low[x]=min(low[x],low[y]);
              }
              else if(instk[y]==True)low[x]=min(low[x],dfn[y]);
      
          }
          if(low[x]==dfn[x])
          {
              cnt++;
              for(int z=-1;z!=x;)
              {
                 z=stk.top();stk.pop();instk[z]=False;
                 scc[z]=cnt;
              }
          }
      }
      
      int main()
      {
          int n,m;
          while(scanf("%d",&n)!=EOF&&n)
          {
              scanf("%d",&m);
              memset(G,0,sizeof(G));
              for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y);
          
              tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
              memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
              for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);
       
              vector<int>cd(cnt+1);//所在连通分支没有出度的点为sink点 
              for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j])cd[scc[i]]++;
              for(int i=1;i<=n;i++)if(cd[scc[i]]==0)printf("%d ",i);
              printf("\n");
          }
          return 0;
      }
      • 1

      信息

      ID
      347
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      247
      已通过
      58
      上传者