Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem B: The Largest Clique

Given a directed graph G, consider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Create a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the transitive closure of G.

We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique.

The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50,000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G.

For each test case, output a single integer that is the size of the largest clique in T(G).

Sample input

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

Output for sample input

4

---

Zachary Friggstad

Clique 的定義跟我們平常想得不太一樣，
原本的定義是原本就有互相連通的關係子圖，在給定的隨意關係圖中尋找一個完全連接子圖。
原本是個 NP-hard 問題

好，這裡的 Clique 只的是一團內，有 semiconnected 即可，即任何兩點 u ~> v or v ~> u。

那麼將 SCC 縮點，然後會變成 DAG 圖，在其中找一條最長路徑即可，
在這裡最長路徑上面會有權重。

縮點之後，可以用拓樸排序在 O(V+E) 時間內進行 Dynamic programming 計算最長路徑，
又或者使用記憶化搜索計算之，下面使用記憶化搜索的方式進行。

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
vector<int> g[1005], dag[1005];
int vfind[1005], findIdx;
int stk[1005], stkIdx;
int in_stk[1005], visited[1005];
int contract[1005];
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int dp[1005], contSize[1005];
int dfs(int nd) {
    if(dp[nd])  return dp[nd];
    int ret = 0;
    for(int i = 0; i < dag[nd].size(); i++)
        ret = max(ret, dfs(dag[nd][i]));
    dp[nd] = ret + contSize[nd];
    return dp[nd];
}
int main() {
    int testcase, n, m;
    int x, y, i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++) {
            g[i].clear();
            dag[i].clear();
        }
        while(m--) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
        }
        // SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        for(i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        memset(dp, 0, sizeof(dp));
        memset(contSize, 0, sizeof(contSize));
        for(i = 1; i <= n; i++) {
            x = contract[i];
            contSize[x]++;
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y)
                    dag[x].push_back(y);
            }
        }
        // dp for a longest path
        int ret = 0;
        for(i = 1; i <= n; i++)
            ret = max(ret, dfs(contract[i]));
        printf("%d\n", ret);
    }
    return 0;
}