UVA11324 The Largest Clique（Tarjan缩点+DAG图简单dp）

The Largest Clique

Description

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

链接

https://vjudge.net/problem/UVA-11324

代码

StatusAccepted
Time90ms
Length2578
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 1010;
vector <int> E[maxn];
vector <int> G[maxn];
int n, m;
int tot, scc_cnt;

int dfn[maxn], low[maxn], sccno[maxn], sccnum[maxn], dp[maxn];
bool vis[maxn];
stack <int> s;

void tarjan(int x) // 求强连通分量
{
dfn[x] = low[x] = ++tot;
s.push(x);
vis[x] = true;
for (int i = 0; i < G[x].size(); ++i)
{
int v = G[x][i];
if (!dfn[v])
{
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if (vis[v])
low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x])
{
++scc_cnt;
while (1)
{
int u = s.top();
s.pop();
vis[u] = 0;
sccno[u] = scc_cnt;
sccnum[scc_cnt]++;
if (u == x)
break;
}
}
}

void find_scc()
{
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(vis));
memset(low, 0, sizeof(low));
memset(sccno, 0, sizeof(sccno));
memset(sccnum, 0, sizeof(sccnum));
tot = scc_cnt = 0;
for (int i = 0; i < n; ++i)
if (!dfn[i])
tarjan(i);
}

int search(int x) // dp找最大点集
{
if (dp[x] != -1)
return dp[x];
dp[x] = sccnum[x];
for (int i = 0; i < E[x].size(); ++i)
{
int v = E[x][i];
dp[x] = max(dp[x], search(v) + sccnum[x]);
}
return dp[x];
}

int main()
{
int T, u, v;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; ++i) // 坑
{
G[i].clear();
E[i].clear();
}
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
u--;
v--;
G[u].push_back(v);
}
find_scc();
memset(dp, -1, sizeof(dp));
for (int u = 0; u < n; ++u) // 缩点建图
{
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (sccno[u] != sccno[v])
E[sccno[u]].push_back(sccno[v]);
}
}
int ans = 0;
for (int i = 1; i <= scc_cnt; ++i)
ans = max(ans, search(i));
printf("%d\n", ans);
}
return 0;
}

The end,
2018-04-24 星期二

1. 太傅不哭@(勉强)

1. @CongTsang#(中枪)