算法分析

• 跑一次拓扑排序整理出所有编号在图中的前后关系

• dist[i]：表示i点在拓扑图中离起点的最远距离(可能存在多起点)，dist[起点] == 100,边的权值为1

时间复杂度 $O(n + m)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N = 10010,M = 20010;
    static int n;
    static int m;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] qv = new int[N];
    static int qidx = 0;
    static int[] d = new int[N];
    static int[] dist = new int[N];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean topsort()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 1;i <= n;i ++)
        {
            if(d[i] == 0)
            {
                q.add(i);
                qv[qidx ++] = i;
            }
        }

        while(!q.isEmpty())
        {
            int t = q.poll();

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if(-- d[j] == 0)
                {
                    q.add(j);
                    qv[qidx ++] = j;
                }

            }
        }
        return qidx == n;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(b,a);
            d[a] ++;
        }

        if(!topsort()) System.out.println("Poor Xed");
        else 
        {
            for(int i = 1;i <= n;i ++) dist[i] = 100;

            for(int i = 0;i < qidx;i ++)
            {
                int j = qv[i];
                for(int k = h[j];k != -1;k = ne[k])
                {
                    int x = e[k];
                    dist[x] = Math.max(dist[x], dist[j] + 1);
                }
            }

            int res = 0;
            for(int i = 1;i <= n;i ++) res += dist[i];
            System.out.println(res);
        }
    }
}

c ++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10010, M = 20010;

int n, m;
int f[N];
int d[N], q[N], qidx = 0;
int h[N], e[M], ne[M], idx = 0;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
    queue<int> q;
    int cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(d[i] == 0)
        {
            q.push(i);
        }

    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        cnt ++;
        for(int i = h[t]; i != -1;i = ne[i])
        {
            int j = e[i];

            f[j] = max(f[j], f[t] + 1);

            d[j] --;
            if(d[j] == 0)
            {
                q.push(j);
            }
        }
    }
    if(cnt == n) return true;
    return false;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a] ++;
    }

    if(!topsort()) puts("Poor Xed");
    else
    {
        int res = 0;
        for(int i = 1;i <= n;i ++)
        {
            res += f[i] + 100;
        }

        cout  << res << endl;
    }
}