题目链接:http://vjudge.net/contest/141990#problem/B
题意:
给一张有向图G,求一个结点集数最大的结点集,是的该结点集中任意两个结点 u 和 v,满足: 要么 u 能到达 v,要么 v 能到达 u 或者 u 和 v 可以互达 ;
这个和有向强连通图很像,连通方式改了,强连通分量是 任意 两点 之间 都可以互达。可以发现一个强连通分量 ,要么全选,要么全部选。
思路:
把一个强连通分量看成一个结点,这个结点有权值,是他的大小,把每个强连通分量看成一个结点,这样 SCC 图就出来了,SCC图 他是一个有向无环图 DAG。
于是就可以用 dp 来做。
坑点:(数据有可能一个结点都没有)
#include <bits/stdc++.h>
using namespace std; const int Maxn = + ; vector<int> G[Maxn];
int pre[Maxn];
int lowlink[Maxn];
int sccno[Maxn];
int dfs_clock;
int scc_cnt;
int n,m; stack<int> S; void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if(!sccno[v])
{
lowlink[u] = min(lowlink[u], pre[v]);
}
}
if(lowlink[u] == pre[u])
{
scc_cnt++;
for(;;)
{
int x = S.top();
S.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
} void find_scc(int)
{
dfs_clock = scc_cnt = ;
memset(pre,,sizeof(pre));
memset(sccno,,sizeof(sccno)); for(int i=; i<n; i++)
{
if(!pre[i])
dfs(i);
}
} int size[Maxn], TG[Maxn][Maxn];
int d[Maxn]; int dp(int u)
{
int& ans = d[u];
if(ans >= ) return ans;
ans = size[u];
for(int v = ; v <= scc_cnt; v++)
if(u != v && TG[u][v])
ans = max(ans, dp(v) + size[u]);
return ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
G[i].clear(); for(int i=; i<m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
u--;
v--;
G[u].push_back(v);
} find_scc(n); memset(size,,sizeof(size));
memset(TG,,sizeof(TG)); for(int i=; i<n; i++)
{
size[sccno[i]] ++;
for(int j=; j<G[i].size(); j++)
{
TG[sccno[i]][sccno[G[i][j]]] = ;
}
}
int ans = ;
memset(d,-,sizeof(d));
for(int i=; i<=scc_cnt; i++)
ans = max(ans,dp(i)); printf("%d\n",ans);
}
return ;
}