题目描述：在有向图里找最大的结点集，使得结点集内的任意两点可以至少单向连通。 1.首先，对于强连通分量里的任意两点都是可以互相到达的，所以我们只需要找一条单向路径把尽量多的强连通分量串起来，就能得到最大的结点集。 2.具体做法就是找出所有强连通块，然后缩点，将图转变成一张无环有向图，每个点的权值就是该点代表的连通块内点的数量，我们就要找出一条权值和最大的路径，使用DP求解，dp[i]表示以连通块i为起点最大权值和路径的权值。
#include<stdio.h>#include<algorithm>#include<string.h>#include<iostream>#include<stack>#include<vector>using namespace std;const int maxn=1005;int n,m;int sccno[maxn];int PRe[maxn];int lowl[maxn];bool map[maxn][maxn];bool v[maxn];int val[maxn];int ans=0;int dp[maxn];vector<int> e[maxn];int dfs_clock,scc_cnt;stack<int> s;void dfs(int u){//find scc pre[u]=lowl[u]=++dfs_clock; s.push(u); for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!pre[v]){ dfs(v); lowl[u]=min(lowl[u],lowl[v]); } else if(!sccno[v]){ lowl[u]=min(lowl[u],pre[v]); } } if(lowl[u]==pre[u]){ scc_cnt++; while(1){ int x=s.top();s.pop(); sccno[x]=scc_cnt; if(x==u)break; } }}void find_scc(int n){ memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); dfs_clock=scc_cnt=0; while(!s.empty())s.pop(); for(int i=0;i<n;i++){ if(!pre[i])dfs(i); }}int DP(int cnt){ if(v[cnt])return dp[cnt]; v[cnt]=1; for(int i=1;i<=scc_cnt;i++){ if(i==cnt)continue; if(map[cnt][i])dp[cnt]=max(dp[cnt],DP(i)+val[cnt]); } ans=max(ans,dp[cnt]);}int main(){ int t,x,y; scanf("%d",&t); while(t--){ ans=0; memset(map,0,sizeof(map)); memset(v,0,sizeof(v)); memset(dp,0,sizeof(dp)); memset(val,0,sizeof(val)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){e[i].clear ();} for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); x--,y--; e[x].push_back(y); } find_scc(n); for(int i=0;i<n;i++){ val[sccno[i]]++; } for(int i=0;i<n;i++){ for(int j=0;j<e[i].size();j++){ if(sccno[i]==sccno[e[i][j]])continue; map[sccno[i]][sccno[e[i][j]]]=1; } } for(int i=1;i<=scc_cnt;i++){ dp[i]=val[i]; } for(int i=1;i<=scc_cnt;i++){ if(!v[i]){DP(i);} } printf("%d/n",ans); } return 0;}新闻热点
疑难解答
