zoj 3795 Grouping tarjan缩点 + DGA上的最长路

时间：2021-05-27 14:58:54
Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The i-th message shows that the age of person si is not smaller than the age of person ti. Now we need to divide all these N people into several groups. One's age shouldn't be compared with each other in the same group, directly or indirectly. And everyone should be assigned to one and only one group. The task is to calculate the minimum number of groups that meet the requirement.

Input

There are multiple test cases. For each test case: The first line contains two integers N(1≤ N≤ 100000), M(1≤ M≤ 300000), N is the number of people, and M is is the number of messages. Then followed by M lines, each line contain two integers si and ti. There is a blank line between every two cases. Process to the end of input.

Output

For each the case, print the minimum number of groups that meet the requirement one line.

Sample Input

4 4

1 2

1 3

2 4

3 4

Sample Output

3

Hint

set1= {1}, set2= {2, 3}, set3= {4}

思路：题目给出a, b  是指a不小于b， 即a可以等于b， a到b拉一条有向边，多个相等的时候会成环，直接求最长路则会死循环, 所以应该先用tarjan把强联通分量缩成一个点，点权就代表该强联通分量中点的数目，再求最长路

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <map>

#include <stack>

#include <vector>

using namespace std;

const int N = 211111;

const int E = 333333;

vector<int> G[N];

int pre[N], low[N], sccno[N], num[N], dfs_ck, scc_cnt;

stack<int> s;

void dfs(int u)

{

    pre[u] = low[u] = ++dfs_ck;

    s.push(u);

    for(int i = 0; i < G[u].size(); ++i) {

        int v = G[u][i];

        if(!pre[v]) {

            dfs(v);

            low[u] = min(low[u], low[v]);

        } else if(!sccno[v]) {

            low[u] = min(low[u], pre[v]);

        }

    }

    if(low[u] == pre[u])

    {

        scc_cnt++;

        for(;;) {

            num[scc_cnt]++;

            int x = s.top(); s.pop();

            sccno[x] = scc_cnt;

            if(x == u) break;

        }

    }

}

void find_scc(int n)

{

    dfs_ck = scc_cnt = 0;

    memset(sccno, 0, sizeof sccno);

    memset(pre, 0, sizeof pre);

    memset(num, 0, sizeof num);

    for(int i = 1; i <= n; ++i) if(!pre[i]) dfs(i);

}

int dp[N];

vector<int> G2[N];

void init(int n)

{

    for(int i = 0; i <= n; ++i) G[i].clear();

    for(int i = 0; i <= n; ++i) G2[i].clear();

    while(!s.empty()) s.pop();

}

int get(int u)

{

    int& res = dp[u];

    if(res != -1) return res;

    res = num[ u ]; // 一开始写成 res = num[ sccno[u] ], wa， 建图的时候已经是通过scc编号来建图了

    int sx = G2[u].size();

    for(int j = 0; j < sx; ++j) res = max(res, get(G2[u][j]) + num[ u ]);

    return res;

}

int main()

{

    int n, m;

    while(~scanf("%d%d", &n, &m))

    {

        int u, v;

        init(n);

        for(int i = 0; i < m; ++i) {

            scanf("%d%d", &u, &v);

            G[u].push_back(v);

        }

        find_scc(n);

       // printf("%d\n", scc_cnt);

    //   for(int i = 1; i <= n; ++i) printf("%d %d\n", i, sccno[i]);

        for(int i = 1; i <= n; ++i) {

            int sx = G[i].size();

            for(int j = 0; j < sx; ++j) {

                int v = G[i][j];

                if(sccno[i] != sccno[v]) {

                    G2[ sccno[i] ].push_back(sccno[v]); //通过scc编号来建图

               //    printf("%d %d\n", sccno[i], sccno[v]);

                }

            }

        }

        memset(dp, -1, sizeof dp);

        int ans = 0;

        for(int i = 1; i <= scc_cnt; ++i) ans = max(ans, get(i));

        printf("%d\n", ans);

    }

}

　　

相关文章