请人做网站收费多少,如何添加wordpress主题,国外空间设计网站,沈阳做网站公司哪家好题意#xff1a;给定一个有向图#xff0c;寻找一个点数最大集合#xff0c;使得这个集合中的任意两个点 u,v, 都有u-v 或者 v-u 或者uv 思路#xff1a;首先将强连通分量通过tarjan算法求出来#xff0c;然后进行缩点#xff0c;也就是每一个缩点 所组成… 题意给定一个有向图寻找一个点数最大集合使得这个集合中的任意两个点 u,v, 都有u-v 或者 v-u 或者uv 思路首先将强连通分量通过tarjan算法求出来然后进行缩点也就是每一个缩点 所组成的图就是一个DAG图令每一个点的权值就是这个缩点所包含节点也就是对应的 强连通分量的节点数目因为强连通分量的任意的两个节点都是相互可达的那么这个 缩点要么选要么不选问题就转换成了DAG图上的最长路径 1 #includeiostream2 #includequeue3 #includestack4 #includecstring5 #includecstdio6 #includealgorithm7 #includevector8 #define N 10059 using namespace std;10 11 struct EDGE{12 int u, v, nt;13 EDGE(){}14 EDGE(int u, int v, int nt) : u(u), v(v), nt(nt){}15 };16 17 int first[N];18 vectorEDGEg;19 vectorEDGEgg;20 int scc_cnt, dfs_clock;21 int scc[N];22 int pre[N], low[N];23 int dp[N], cnt[N];24 25 int in[N];26 int n, m;27 stackints;28 29 void dfs(int u){30 pre[u] low[u] dfs_clock;31 s.push(u);32 for(int i first[u]; ~i; i g[i].nt){33 int v g[i].v;34 if(!pre[v]){35 dfs(v);36 low[u] min(low[u], low[v]);37 }else if(!scc[v])38 low[u] min(low[u], pre[v]);39 }40 if(low[u] pre[u]){41 scc_cnt;42 while(1){43 cnt[scc_cnt];44 int x s.top(); s.pop();45 scc[x] scc_cnt;46 if(xu) break;47 }48 }49 }50 51 void addEdge(int u, int v){52 g.push_back(EDGE(u, v, first[u]));53 first[u] g.size() - 1;54 }55 56 void tarjans(){57 memset(pre, 0, sizeof(pre));58 memset(scc, 0, sizeof(scc));59 memset(cnt, 0, sizeof(cnt));60 memset(dp, 0, sizeof(dp));61 memset(in, 0, sizeof(in));62 scc_cnt 0;63 dfs_clock 0;64 for(int i1; in; i)65 if(!pre[i]) dfs(i);66 int len g.size();67 memset(first, -1, sizeof(first));68 gg.clear();69 for(int i0; ilen; i)70 if(scc[g[i].u] ! scc[g[i].v]){71 in[scc[g[i].v]];72 gg.push_back(EDGE(scc[g[i].u], scc[g[i].v], first[scc[g[i].u]]));73 first[scc[g[i].u]] gg.size() - 1;74 }75 int maxN 0; 76 queueintq;77 for(int i1; iscc_cnt; i)78 if(!in[i]){79 dp[i] cnt[i];80 q.push(i);81 if(maxN dp[i]) maxN dp[i];82 }83 while(!q.empty()){84 int u q.front(); q.pop();85 for(int ifirst[u]; ~i; i gg[i].nt){86 int v gg[i].v;87 dp[v] max(dp[v], dp[u] cnt[v]);88 q.push(v);89 if(maxN dp[v]) maxN dp[v];90 }91 }92 printf(%d\n, maxN); 93 }94 95 int main(){96 int t;97 scanf(%d, t);98 while(t--){99 memset(first, -1, sizeof(first));
100 scanf(%d%d, n, m);
101 while(m--){
102 int u, v;
103 scanf(%d%d, u, v);
104 addEdge(u, v);
105 }
106 tarjans();
107 g.clear();
108 }
109 return 0;
110 } View Code 转载于:https://www.cnblogs.com/hujunzheng/p/4019695.html
