首页 > 代码库 > UVA 11324.The Largest Clique tarjan缩点+拓扑dp
UVA 11324.The Largest Clique tarjan缩点+拓扑dp
题目链接：https://vjudge.net/problem/UVA-11324
题意：求一个有向图中结点数最大的结点集，使得该结点集中任意两个结点u和v满足：要目u可以到达v，要么v可以到达u（相互可达也可以）。
思路：同一个强联通分量中满足结点集中任意两个结点u和v满足：要目u可以到达v，要么v可以到达u（相互可达也可以）。把强联通分量收缩点后得到scc图，让每个scc结点的权值等于他的结点数，则求scc图上权最大的路径。拓扑dp，也可以直接bfs，但是要建立一个新的起点，连接所有入度为0的结点。
代码：
#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<map>#include<queue>#include<stack>#include<vector>using namespace std;typedef long long ll;const int MAXN=2e5+100,INF=0x3f3f3f3f,MOD=1e9+7;map<int,vector<int> >G;int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_color,scc_cut;stack<int>S;map<int,vector<int> >NG;int deg[MAXN];int in[MAXN];void dfs(int u){ pre[u]=lowlink[u]=++dfs_color; S.push(u); for(int i=0; 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],lowlink[v]); } if(lowlink[u]==pre[u]) { scc_cut++; while(!S.empty()) { int x=S.top(); S.pop(); sccno[x]=scc_cut; deg[scc_cut]++; if(x==u) break; } }}void find_scc(int n){ dfs_color=scc_cut=0; memset(pre,0,sizeof(pre)); memset(sccno,0,sizeof(sccno)); memset(deg,0,sizeof(deg)); for(int i=1; i<=n; i++) if(!pre[i]) dfs(i);}void re_build(int n){ for(int i=1; i<=scc_cut; i++) in[i]=0,NG[i].clear(); for(int u=1; u<=n; u++) { for(int i=0; i<G[u].size(); i++) { int v=G[u][i]; if(sccno[u]==sccno[v]) continue; in[sccno[v]]++; NG[sccno[u]].push_back(sccno[v]); } } for(int i=1; i<=n; i++) G[i].clear();}queue<int>q;int ans[MAXN];void topsort(){ memset(ans,0,sizeof(ans)); for(int i=1; i<=scc_cut; i++) if(in[i]==0) ans[i]=deg[i],q.push(i); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<NG[u].size(); i++) { int v=NG[u][i]; ans[v]=max(ans[v],ans[u]+deg[v]); in[v]--; if(in[v]==0) q.push(v); } }}int main(){ int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } find_scc(n); re_build(n); topsort(); int Max=0; for(int i=1; i<=scc_cut; i++) Max=max(Max,ans[i]); cout<<Max<<endl; } return 0;}
UVA 11324.The Largest Clique tarjan缩点+拓扑dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。