[UVA][SCC] 11324 - The Largest Clique
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;
}