全球彩票平台_全球彩票注册平台|官网下载地址

热门关键词: 全球彩票平台,全球彩票注册平台,全球彩官网下载地址

全球彩票注册平台小白入门向,爱在心中

习题:codevs 2822 爱在心里 解题报告,codevs2822

这一次的解题报告是有关tarjan算法的一道思维量一点都不小的主题材料(真的是原创小说,希望管理员不要再把稿子移出首页)。

那道题花梗莲以前做过,然则后天出于要复习tarjan算法,于是就见到codevs分类强联通分量里面独有这一道题。

难点是如此的:

“每个人都拥有一个梦,即使彼此不相同,能够与你分享,无论失败成功都会感动。爱因为在心中,平凡而不平庸,世界就像迷宫,却又让我们此刻相逢Our Home。”

在爱的国度里有N个人,在他们的心中都有着一个爱的名单,上面记载着他所爱的人(不会出现自爱的情况)。爱是具有传递性的,即如果A爱B,B爱C,则A也爱C。
如果有这样一部分人,他们彼此都相爱,则他们就超越了一切的限制,用集体的爱化身成为一个爱心天使。
现在,我们想知道在这个爱的国度里会出现多少爱心天使。而且,如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的,否则输出-1。

那是一个有向图上的主题素材,这道题很轻松看出来三个慈善精灵就是一批人互相爱然后结成的有向环。既然是有向的图求强联通分量,套上tarjan就行了。不过因为背后要出口爱心Smart是由何人结合的,所以,大家须要记录各样人在哪个爱心Smart内部,具体tarjan标程正是上边那样:

 1 void dfs(int u){
 2     low[u] = dfn[u] =   dfs_clock;
 3     s.push(u);
 4     for(int i = 0;i < g[u].size();  i){
 5         int v = g[u][i];
 6         if(!dfn[v]){
 7             dfs(v);
 8             low[u] = min(low[u],low[v]);
 9         }
10         else if(!ind[v]){
11             low[u] = min(low[u],dfn[v]);
12         }
13     }
14     if(low[u] == dfn[u]){
15         scc_cnt  ;
16         while(1){
17             int x = s.top();
18             s.pop();
19             ind[x] = scc_cnt;
20             sccno[scc_cnt]  ;
21             if(x == u)break;
22         }
23     }
24 }
25 void find_scc(int n){
26     dfs_clock = scc_cnt = 0;
27     for(int i = 1;i <= n;  i){
28         if(!dfn[i])dfs(i);
29     }
30 }

假若有不懂的地点,就印证是tarjan算法照旧没搞懂,请先化解tarjan算法的基本功再来看这道题。

下一场正是求每一个爱心Smart被有些个人爱着(爱心Smart也被属于它本身的公众爱着)。由于爱有传递性,大家很轻易能体会领会传递闭包的题材。具体做法正是:

1.先求出来有所的仁义Smart(在此地一位也当作是一个慈祥Smart,可是出口爱心Smart个数的时候,一位组合的慈善Smart是不算的)和那一个慈善Smart由几人组成。

2.给各样爱心天使编号(缩点),然后营造贰个以“被爱”为方向的新的有向图。

3.在新的有向图中跑SPFA(为何不用Floyd,这一个时刻复杂度太高了,所以我们还是选择scc_cnt遍的SPFA,时间复杂度最坏也等于O(nke),保险是超不了时间的。SPFA在此地起到的职能就是总结各样爱心Smart的爱能或无法传递到有些Smart)。

4.总结计数,假若size[有些爱心Smart] == n的话,那么就按编号从小到大遍历各样人输出这么些慈祥Smart由哪些人组成。若无别的七个慈善Smart的size为n的话,(用一个数笔录,假如b == 0)就输出-1.

然后展现总体代码,依旧不是很短,才刚139行。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <stack>
  7 #include <vector>
  8 #include <set>
  9 #include <queue>
 10 using namespace std;
 11 const int maxn = 1005;
 12 int dfn[maxn],low[maxn],dfs_clock,n,ind[maxn],m,scc_cnt,a,b,size[maxn],sccno[maxn],tim = 0;
 13 struct edge{
 14     int u,v;
 15     edge(int a,int b):u(a),v(b){};
 16 };
 17 struct edges{
 18     int to,next,cost;
 19 }qmap[maxn<<3];
 20 vector<int>g[maxn];
 21 vector<int>gk[maxn];
 22 vector<edge>ga;
 23 int d[maxn],h[maxn];
 24 const int INF = 10000000;
 25 stack<int> s;
 26 void add(int u,int v){
 27     qmap[tim].to = v;qmap[tim].cost = 1;qmap[tim].next = h[u];h[u] = tim  ;
 28 }
 29 void init(int n){
 30     memset(dfn,0,sizeof(dfn));
 31     memset(low,0,sizeof(low));
 32     memset(ind,0,sizeof(ind));
 33     memset(size,0,sizeof(size));
 34     memset(sccno,0,sizeof(sccno));
 35     memset(h,-1,sizeof(h));
 36     for(int i = 1;i <= n;  i){
 37         g[i].clear();
 38         gk[i].clear();
 39     }
 40 }
 41 void dfs(int u){
 42     low[u] = dfn[u] =   dfs_clock;
 43     s.push(u);
 44     for(int i = 0;i < g[u].size();  i){
 45         int v = g[u][i];
 46         if(!dfn[v]){
 47             dfs(v);
 48             low[u] = min(low[u],low[v]);
 49         }
 50         else if(!ind[v]){
 51             low[u] = min(low[u],dfn[v]);
 52         }
 53     }
 54     if(low[u] == dfn[u]){
 55         scc_cnt  ;
 56         while(1){
 57             int x = s.top();
 58             s.pop();
 59             ind[x] = scc_cnt;
 60             sccno[scc_cnt]  ;
 61             if(x == u)break;
 62         }
 63     }
 64 }
 65 void find_scc(int n){
 66     dfs_clock = scc_cnt = 0;
 67     for(int i = 1;i <= n;  i){
 68         if(!dfn[i])dfs(i);
 69     }
 70 }
 71 void spfa(int x){
 72     for(int i = 1;i <= scc_cnt;  i){
 73         d[i] = INF;
 74     }
 75     bool visit[maxn];
 76     memset(visit,false,sizeof(visit));
 77     d[x] = 0;
 78     queue<int>q;
 79     q.push(x);
 80     visit[x] = true;
 81     while(!q.empty()){
 82         int y = q.front();
 83         q.pop();visit[y] = false;
 84         for(int i = h[y];i != -1;i = qmap[i].next){
 85             edges e = qmap[i];
 86             if(d[y]   e.cost < d[e.to]){
 87                 d[e.to] = d[y]   e.cost;
 88                 if(!visit[e.to]){
 89                     q.push(e.to);
 90                     visit[e.to] = true;
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 void work(int i){
 97     spfa(i);
 98     for(int k = 1;k <= scc_cnt;  k){
 99         if(k == i)continue;
100         if(d[k] == INF)continue;
101         size[i]  = sccno[k];
102     }
103     if(size[i] == n){
104         b = 1;
105         for(int j = 1;j <= n;  j){
106             if(ind[j] == i)printf("%d ",j);
107         }
108         printf("n");
109     }
110     return;
111 }
112 int main(){
113     scanf("%d%d",&n,&m);
114     init(n);
115     for(int i = 1;i <= m;  i){
116         scanf("%d%d",&a,&b);
117         g[a].push_back(b);
118         gk[b].push_back(a);
119         ga.push_back(edge(b,a)); 
120     }
121     find_scc(n);
122     int ans = scc_cnt;
123     for(int i = 1;i <= scc_cnt;  i){
124         if(sccno[i] == 1)ans--;
125     }
126     printf("%dn",ans);
127     for(int i = 0;i < ga.size();  i){
128         add(ind[ga[i].u],ind[ga[i].v]);
129     }
130     for(int i = 1;i <= scc_cnt;  i){
131         size[i] = sccno[i];
132     }
133     b = 0;
134     for(int i = 1;i <= scc_cnt;  i){
135         if(sccno[i] != 1)work(i);
136     }
137     if(b == 0)printf("-1n");
138     return 0;
139 }

此次的解题报告就到此地,磨芋继续去刷题了。还可能有假设极度来讲,请联系笔者的信箱[email protected]向小编留言。

2822 爱在内心 解题报告,codevs2822 本次的解题报告是关于tarjan算法的一道思维量十分的大的问题(真的是原创小说,希望助理馆员不...

这一次的解题报告是有关tarjan算法的一道思维量不小的难点(真的是原创文章,希望助理馆员不要再把稿子移出首页)。

此次的解题报告是有关tarjan算法的一道思维量一点都不小的问题(真的是原创文章,希望管理员不要再把稿子移出首页)。

一、【前言】关于tarjan

tarjan算法是由Robert Tarjan建议的求解有向图强连通分量的算法。

那就是说难点来了找蓝翔!(划掉)什么是强连通分量?

我们定义:要是五个顶峰相互衔接(即存在A到B和B到A的通路),则称那多个点强连通。对于二个有向图G,假使G中肆意两点都强连通,则称G是一个强连通图。有向图的急剧强连通子图,称为该图的强连通分量。

对于下图,{1,2,3,4}、{5}、{6}分别是它的强连通分量。

全球彩票注册平台 1

那么tarjan是什么样找到那么些强连通分量的吗?

简单tarjan正是dfs,各种强连通分量都以寻找树中的一颗子树。寻觅时,大家把当下探求树中未管理过的点加入二个储藏室,回溯时从栈顶依次抽取成分判定他们是还是不是属于一个强连通分量。

咱俩对dfs的经过中增加如下概念:
1、dfn[i]:代表寻觅点i的前后相继编号;

2、low[i]:代表点i所能回溯到的栈中最初的次第编号。

当dfn[i]=low[i]时,以i为根的子树上的全数一点便构成八个强连通分量。

 

一、【前言】关于tarjan

tarjan算法是由罗伯特 Tarjan提出的求解有向图强连通分量的算法。

那么难题来了找蓝翔!(划掉)什么是强连通分量?

小编们定义:假如多个终端相互衔接(即存在A到B和B到A的通路),则称那八个点强连通。对于三个有向图G,假诺G中率性两点都强连通,则称G是二个强连通图。有向图的巨大强连通子图,称为该图的强连通分量。

对此下图,{1,2,3,4}、{5}、{6}分别是它的强连通分量。

全球彩票注册平台 2

那么tarjan是如何找到那几个强连通分量的啊?

粗略tarjan正是dfs,每一个强连通分量都以探索树中的一颗子树。搜索时,大家把当下寻觅树中未管理过的点步入二个仓房,回溯时从栈顶依次抽出成分剖断他们是还是不是属于三个强连通分量。

作者们对dfs的进度中增多如下概念:
1、dfn[i]:代表寻觅点i的主次编号;

2、low[i]:代表点i所能回溯到的栈中最早的程序编号。

当dfn[i]=low[i]时,以i为根的子树上的全部一些便构成一个强连通分量。

 

这道题磨芋在此之前做过,可是前天出于要复习tarjan算法,于是就看到codevs分类强联通分量里面独有这一道题。

这道题魔芋在此以前做过,可是后天由于要复习tarjan算法,于是就看到codevs分类强联通分量里面唯有这一道题。

二、tarjan算法c语言完结

那便是说要哪些利用程序来兑现tarjan算法呢?

大约思路如下:
1、从三个未被管理过的点i初始,给它构成一个前后相继编号并把它压入栈中,然后标志点表示其已入栈,令low[i]=dfn[i]=次序编号;

2、遍历每条以i为源点的边,若边的终极j未被管理过,就对其进展操作1~3,令low[i]=min(low[i],low[j]);

3、找到的点j如若被拍卖过,则判定其是还是不是在栈中:若在,则令low[i]=min(low[i],dfn[j]);

4、若是dfn[i]=low[i],就将栈顶到i间的具备因素弹出,它们正是二个强连通分量;

5、重复1~4,直至不设有一些未被处理。

贴上伪代码(转自百度百科词条——tarjan算法)

全球彩票注册平台 3全球彩票注册平台 4

 1 tarjan(u)
 2 {
 3     DFN[u]=Low[u]=  Index//为节点u设定次序编号和Low初值
 4     Stack.push(u)//将节点u压入栈中
 5     for each(u,v) in E//枚举每一条边
 6         if (visnotvisted)//如果节点v未被访问过
 7             tarjan(v)//继续向下找
 8             Low[u]=min(Low[u],Low[v])
 9         else if (vinS)//如果节点v还在栈内
10                 Low[u]=min(Low[u],DFN[v])
11     if (DFN[u]==Low[u])//如果节点u是强连通分量的根
12     repeat{
13         v=S.pop//将v退栈,为该强连通分量中一个顶点
14         printv
15         until(u==v)
16     }

tarjan伪代码

二、tarjan算法c语言实现

那么要怎么利用程序来贯彻tarjan算法呢?

大约思路如下:
1、从一个未被拍卖过的点i开首,给它构成二个顺序编号并把它压入栈中,然后标识点表示其已入栈,令low[i]=dfn[i]=次序编号;

2、遍历每条以i为源点的边,若边的极端j未被拍卖过,就对其举行操作1~3,令low[i]=min(low[i],low[j]);

3、找到的点j假使被管理过,则判别其是不是在栈中:若在,则令low[i]=min(low[i],dfn[j]);

4、若是dfn[i]=low[i],就将栈顶到i间的持有因素弹出,它们就是多少个强连通分量;

5、重复1~4,直至空头支票点未被管理。

贴上伪代码(转自百度百科词条——tarjan算法)

全球彩票注册平台 5全球彩票注册平台 6

 1 tarjan(u)
 2 {
 3     DFN[u]=Low[u]=  Index//为节点u设定次序编号和Low初值
 4     Stack.push(u)//将节点u压入栈中
 5     for each(u,v) in E//枚举每一条边
 6         if (visnotvisted)//如果节点v未被访问过
 7             tarjan(v)//继续向下找
 8             Low[u]=min(Low[u],Low[v])
 9         else if (vinS)//如果节点v还在栈内
10                 Low[u]=min(Low[u],DFN[v])
11     if (DFN[u]==Low[u])//如果节点u是强连通分量的根
12     repeat{
13         v=S.pop//将v退栈,为该强连通分量中一个顶点
14         printv
15         until(u==v)
16     }

tarjan伪代码

主题材料是那般的:

难点是这么的:

三、codevs1332题解

←_←挂上原题链接

那是一道全♂裸的tarjan题,大家只需跑叁次tarjan,并对富有强连通分量染色,最终输出最大的就好

代码如下:

全球彩票注册平台 7全球彩票注册平台 8

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 struct node
 5 {
 6     int v;
 7     int next;
 8 }e[50010];//邻接表记录有向图 
 9 int stack[5010],top;//栈 
10 int dfn[5010],low[5010],index;//index用于记录次序编号 
11 bool vis[5010];//判断点是否在栈内 
12 int st[5010],cnt; 
13 int color[5010],s[5010],num;//用于染色并记录颜色种类 
14 void build(int a,int b)
15 {
16     e[  cnt].v=b;
17     e[cnt].next=st[a];
18     st[a]=cnt;
19 }//建图,没什么好说的 
20 void tarjan(int x)
21 {
22     dfn[x]=  index;
23     low[x]=index;
24     vis[x]=true;
25     stack[  top]=x;//当前点入栈 
26     int i;
27     for(i=st[x];i!=0;i=e[i].next)//枚举以当前点为起点的边 
28     {
29         int temp=e[i].v;//temp为当前被枚举边的终点 
30         if(!dfn[temp])//如果当前边终点未被处理 
31         {
32             tarjan(temp);
33             low[x]=min(low[x],low[temp]);
34         }
35         else if(vis[temp])low[x]=min(low[x],dfn[temp]);
36     }
37     if(dfn[x]==low[x])
38     {
39         vis[x]=false;
40         color[x]=  num;//给当前强连通分量染上新颜色 
41         s[num]  ;//给当前强连通分量里的点染色 
42         while(stack[top]!=x)//栈顶元素依次出栈 
43         {
44             s[num]  ;
45             color[stack[top]]=num;
46             vis[stack[top--]]=false;
47         }
48         top--;
49     }
50 }
51 int main()
52 {
53     int n,m,i,a,b,t,ans=0,f;
54     scanf("%d%d",&n,&m);
55     for(i=1;i<=m;i  )
56     {
57         scanf("%d%d%d",&a,&b,&t);
58         build(a,b);
59         if(t-1)build(b,a);
60     }
61     for(i=1;i<=n;i  )
62     {
63         if(!dfn[i])tarjan(i);
64     }
65     for(i=1;i<=n;i  )
66     {
67         if(s[color[i]]>ans)//找到被染色最多的强连通分量(因为要求字典序,所以使用'>') 
68         {
69             ans=s[color[i]];
70             f=i;
71         }
72     }
73     printf("%dn",ans);
74     for(i=1;i<=n;i  )
75     {
76         if(color[i]==color[f])printf("%d ",i);//输出被染成最大强连通分量的颜色的点 
77     }
78     return 0;
79 }

codevs1332

弱弱地说一句,本虎掌码字也不便于,转载请申明出处

三、codevs1332题解

←_←挂上原题链接

那是一道全♂裸的tarjan题,大家只需跑一遍tarjan,并对全部强连通分量染色,最终输出最大的就好

代码如下:

全球彩票注册平台 9全球彩票注册平台 10

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 struct node
 5 {
 6     int v;
 7     int next;
 8 }e[50010];//邻接表记录有向图 
 9 int stack[5010],top;//栈 
10 int dfn[5010],low[5010],index;//index用于记录次序编号 
11 bool vis[5010];//判断点是否在栈内 
12 int st[5010],cnt; 
13 int color[5010],s[5010],num;//用于染色并记录颜色种类 
14 void build(int a,int b)
15 {
16     e[  cnt].v=b;
17     e[cnt].next=st[a];
18     st[a]=cnt;
19 }//建图,没什么好说的 
20 void tarjan(int x)
21 {
22     dfn[x]=  index;
23     low[x]=index;
24     vis[x]=true;
25     stack[  top]=x;//当前点入栈 
26     int i;
27     for(i=st[x];i!=0;i=e[i].next)//枚举以当前点为起点的边 
28     {
29         int temp=e[i].v;//temp为当前被枚举边的终点 
30         if(!dfn[temp])//如果当前边终点未被处理 
31         {
32             tarjan(temp);
33             low[x]=min(low[x],low[temp]);
34         }
35         else if(vis[temp])low[x]=min(low[x],dfn[temp]);
36     }
37     if(dfn[x]==low[x])
38     {
39         vis[x]=false;
40         color[x]=  num;//给当前强连通分量染上新颜色 
41         s[num]  ;//给当前强连通分量里的点染色 
42         while(stack[top]!=x)//栈顶元素依次出栈 
43         {
44             s[num]  ;
45             color[stack[top]]=num;
46             vis[stack[top--]]=false;
47         }
48         top--;
49     }
50 }
51 int main()
52 {
53     int n,m,i,a,b,t,ans=0,f;
54     scanf("%d%d",&n,&m);
55     for(i=1;i<=m;i  )
56     {
57         scanf("%d%d%d",&a,&b,&t);
58         build(a,b);
59         if(t-1)build(b,a);
60     }
61     for(i=1;i<=n;i  )
62     {
63         if(!dfn[i])tarjan(i);
64     }
65     for(i=1;i<=n;i  )
66     {
67         if(s[color[i]]>ans)//找到被染色最多的强连通分量(因为要求字典序,所以使用'>') 
68         {
69             ans=s[color[i]];
70             f=i;
71         }
72     }
73     printf("%dn",ans);
74     for(i=1;i<=n;i  )
75     {
76         if(color[i]==color[f])printf("%d ",i);//输出被染成最大强连通分量的颜色的点 
77     }
78     return 0;
79 }

codevs1332

弱弱地说一句,本磨芋码字也不便于,转发请注脚出处

本文由全球彩票平台发布于全球彩票注册平台编程,转载请注明出处:全球彩票注册平台小白入门向,爱在心中

TAG标签: 全球彩票平台
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。