首页 > 代码库 > Uva--11324--The Largest Clique【有向图强连通分量+最大团】
Uva--11324--The Largest Clique【有向图强连通分量+最大团】
链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=25&problem=2299&mosmsg=Submission+received+with+ID+14404690
题意:一个有向图,找一个最大的点集使得任意两点u、v间都存在一条路(单向或双向),问这个点集最大是多少
思路:强连通分量缩点后得到SCC图,使SCC结点的权等于它的节点个数,找一条路径使得权值和最大即可,找路径用dp记忆化搜索
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 1010 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxm = 50010; struct node{ int u, v, next; }edge[maxm], edge1[maxm]; int Stack[MAXN]; int head[MAXN], head1[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN], scc_elem[MAXN]; int scc_cnt, id, cnt, cnt1, top, n, m; int dp[MAXN]; void add_edge(int u, int v, node edge[], int head[], int &cnt){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; } void tarjin(int u){ int i, j; dfn[u] = low[u] = ++id; Stack[top++] = u; for(i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(dfn[v] == -1){ tarjin(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ scc_cnt++; int temp; do{ temp = Stack[--top]; sccno[temp] = scc_cnt; }while(temp != u); } } int dfs_DAG(int u){ if(dp[u] > 0) return dp[u]; dp[u] = scc_elem[u]; for(int i = head1[u]; i != -1; i = edge1[i].next){ int v = edge1[i].v; dp[u] = max(dp[u], scc_elem[u] + dfs_DAG(v)); } return dp[u]; } int main(){ int i, j, t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); cnt = cnt1 = scc_cnt = id = top = 0; memset(head, -1, sizeof(head)); memset(head1, -1, sizeof(head1)); memset(dfn, -1, sizeof(dfn)); memset(sccno, 0, sizeof(sccno)); memset(scc_elem, 0, sizeof(scc_elem)); for(i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); add_edge(u, v, edge, head, cnt); } for(i = 1; i <= n; i++){ if(dfn[i] == -1) tarjin(i); } for(i = 1; i <= n; i++){ int x = sccno[i]; scc_elem[x]++; } for(i = 0; i < cnt; i++){ int u = edge[i].u; int v = edge[i].v; if(sccno[u] != sccno[v]){ add_edge(sccno[u], sccno[v], edge1, head1, cnt1); } } memset(dp, 0, sizeof(dp)); int ans = 0; for(i = 1; i <= scc_cnt; i++){ ans = max(ans, dfs_DAG(i)); } printf("%d\n", ans); } return 0; }
Uva--11324--The Largest Clique【有向图强连通分量+最大团】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。