“浪潮杯”山东省第六届ACM大学生程序设计竞赛 Circle of Friends_但求-_-心安的博客-程序员秘密

先用强联通分量缩点，然后深搜找最短路径就行了，

#include <bits/stdc++.h>
using namespace std;
const int max_V=100005;
vector<int>G[max_V];
vector<int>rG[max_V];
vector<int>vs;
int used[max_V];
int cmp[max_V],cnt[max_V],vis[max_V];
int V;
void dfs(int v)
{
    used[v]=1;
    for(int i=0; i<(int)G[v].size(); i++)
    {
        if(!used[G[v][i]])
            dfs(G[v][i]);
    }
    vs.push_back(v);
}
void rdfs(int v,int k)
{
    cnt[k]++;
    used[v]=1;
    cmp[v]=k;
    for(int i=0; i<(int)rG[v].size(); i++)
    {
        if(!used[rG[v][i]])
            rdfs(rG[v][i],k);
    }
}

int Kosaraju()
{
    int k=0;
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0; v<V; v++)
    {
        if(!used[v])dfs(v);
    }
    memset(used,0,sizeof(used));
    for(int i=V-1; i>=0; i--)
    {
        if(!used[vs[i]])
        {
            rdfs(vs[i],k++);
        }
    }
    return k;
}
int flag=0;
int dfs1(int u,int now)
{
if(used[u]!=-1)return used[u];
 if(cmp[u]==cmp[V-1])
 {flag=1;return now;}
 int ans=100001;
 for(int i=0;i<(int)G[u].size();i++)
 {
     int tmp=G[u][i];
     if(vis[tmp])continue;
     vis[tmp]=1;
     ans=min(ans,dfs1(G[u][i],now+(cmp[u]==cmp[tmp]?0:1)));
     vis[tmp]=0;
 }
 used[u]=ans;
 return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int m,x,y;
    scanf("%d%d",&V,&m);
    for(int i=0;i<V;i++)G[i].clear(),rG[i].clear();
    memset(cnt,0,sizeof(cnt));
    while(m--)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        rG[y].push_back(x);
    }
    Kosaraju();
    if(cmp[0]==cmp[V-1])
        {printf("0\n");
    continue;}
    memset(used,-1,sizeof(used));
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    flag=0;
    dfs1(0,0);
    if(flag==0)
    {
        printf("-1\n");
    continue;
    }
     printf("%d\n",used[0]);
}
    return 0;
}

本文链接：https://blog.csdn.net/clx55555/article/details/80118015

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Android Studio 赛博朋克风注册登录app_影流小白的博客-程序员秘密

结果展示：主界面：登录界面：注册界面：一、设计要求：①主界面供用户选择登录/注册并展示用户昵称、用户ID②登陆界面，点击登录后查询用户输入用户名与密码是否与内设用户名密码一致。一致消息提示登陆成功不一致消息提示登陆失败未填写时以消息提示/对话框方式提醒用户③注册界面，点击注册后跳转至主界面显示用户信息未填写时消息提示二、设计框架：主界面：设置请求码 private static final int REQUEST_REGISTER_CODE = 1; privat

万字好文！14 个 Spring MVC 顶级技巧，随时用随时爽，一直用一直爽_程序员小乐的博客-程序员秘密

点击上方 "后端架构师"关注,星标或置顶一起成长后台回复“大礼包”有惊喜礼包！关注订阅号「后端架构师」，收看更多精彩内容每日英文Miracles sometimes o...

frp构建多级网络代理_frp ip代理_山山而川'的博客-程序员秘密

frp 是一个专注于内网穿透的高性能的反向代理应用，支持 TCP、UDP、HTTP、HTTPS 等多种协议，采用 Golang 编写，支持跨平台，仅需下载对应平台的二进制文件即可执行，没有额外依赖。frp可以将内网服务以安全、便捷的方式通过具有公网 IP 节点的中转暴露到公网。且frp不会被杀软查杀！！frp 有windows和linux两个版本，主要包含以下文件：frps，服务端程序；frps.ini，服务端配置文件。frpc，客户端程序；frpc.ini，客户端配置文件。

《我就是演员》半决赛观后感_《我就是演员》观后感_starrow的博客-程序员秘密

半决赛我觉得最好的一幕就是梅兰芳，真挚动人，余韵绵长。因为节目本质上是综艺，所用的剧本大多追求表面上的好看和刺激，结果就是几乎每一场都有演员泪流满面。梅兰芳这一幕剧，在人物感情的深沉饱满上绝不逊色于其他剧目，然而因为牵涉到复杂的历史背景，线索是艺术家的心路和抉择，不但主题跳出了普通人生活的窠臼，而且思想之深刻和意境之悠远，我觉得也是众多剧目中难得的。我没有看过电影原作，但丝毫不觉得这幕戏有多...

opencv-contrib-python3.4.1.15（python3.7）的whl文件下载地址_织茧的博客-程序员秘密

转载地址：contrib下载地址一定要跟自己的opencv的版本一致，不然就能用了

angular中使用ngx-translate国际化配置_faine℃的博客-程序员秘密

一、ngx-translate认识ngx-translate：The internationalization (i18n) library for Angular.二、安装npm install @ngx-translate/core --savenpm install @ngx-translate/http-loader --save三、项目中配置使用ngx-translate...