洛谷 P1137 旅行計劃

題目描述

小明要去一個國家旅遊。這個國家有N個城市，編号為1～N，并且有M條道路連接配接着，小明準備從其中一個城市出發，并隻往東走到城市i停止。

是以他就需要選擇最先到達的城市，并制定一條路線以城市i為終點，使得線路上除了第一個城市，每個城市都在路線前一個城市東面，并且滿足這個前提下還希望遊覽的城市盡量多。

現在，你隻知道每一條道路所連接配接的兩個城市的相對位置關系，但并不知道所有城市具體的位置。現在對于所有的i，都需要你為小明制定一條路線，并求出以城市i為終點最多能夠遊覽多少個城市。

輸入輸出格式

輸入格式：

輸入的第1行為兩個正整數N, M。

接下來M行，每行兩個正整數x, y，表示了有一條連接配接城市x與城市y的道路，保證了城市x在城市y西面。

輸出格式：

輸出包括N行，第i行包含一個正整數，表示以第i個城市為終點最多能遊覽多少個城市。

輸入輸出樣例

輸入樣例#1：

5 6
1 2
1 3
2 3
2 4
3 4
2 5
      

輸出樣例#1：

1
2
3
4
3
      

說明

均選擇從城市1出發可以得到以上答案。

對于20%的資料，N ≤ 100；

對于60%的資料，N ≤ 1000；

對于100%的資料，N ≤ 100000，M ≤ 200000。

解題思路

　　裸的dfs，就像

這題

。沒看資料範圍，第一次存邊的數組才開了100010，最後一個點爆RE……

　　似乎這類題用BFS時間能少一半

源代碼

#include<cstdio>
#include<algorithm>

int n,m;
struct Edge{
    int next,to;
}e[100010];
int cnt=1,head[200010]={0};
void add(int u,int v)
{
    e[cnt]={head[u],v};
    head[u]=cnt++;
}
int ru[100010]={0};
int max_to[100010]={0};
int dfs(int u)
{
    if(max_to[u]) return max_to[u]; 
    max_to[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        max_to[u]=std::max(max_to[u],dfs(v)+1);
    }
    return max_to[u];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        std::swap(u,v);//要求的是以i為終點的答案，因為習慣存以每個點為起點的答案，于是反向建圖
        ru[v]++;
        add(u,v);
    }
    for(int i=1;i<=n;i++) if(!ru[i]) dfs(i);
    for(int i=1;i<=n;i++) printf("%d\n",max_to[i]);
    return 0;
}