做电商网站要备案吗,东莞网站建设排名 南城,桂林生活网app下载,注册网站地址今天学习了强连通分量。 【参考博客】 如果觉得我讲的有些地方难以理解或者存在问题#xff08;欢迎留言#xff09;#xff0c;可以看一下我借鉴的一些大佬的博客#xff1a; 传送门1 传送门2 【知识储备】 首先我们需要对几个定义有一些概念#xff1a; 强连通#xff…今天学习了强连通分量。 【参考博客】 如果觉得我讲的有些地方难以理解或者存在问题欢迎留言可以看一下我借鉴的一些大佬的博客 传送门1 传送门2 【知识储备】 首先我们需要对几个定义有一些概念 强连通有向图中两个点可以相互到达 强连通图有向图中任意两个点都是强连通的 强连通分量一个有向图的一个子图中是强连通图的最大的子图就称这个有向图为强连通分量
通俗理解的话强连通分量里面的任何两个点都可以相互到达也就是说至少存在一条路径可以访问到所有的点再回到起点可以经过重复的点就好像一个环因此我们用DFS配合专门的算法来解决求连通分量的问题。
【算法介绍】 我们一般用Trajan算法解决相关问题。 正如上面的简单分析所谓的强连通分量就是我们想要找一条可以回到起点的经过尽可能多点的路径那如何判断我们是回到起点或者已经访问过的点呢我们就需要用数组进行标记每个点的状态来方便我们进行判断。 这里引入两个关键的数组 DFN[MAXN]DFN[ MAXN ]DFN[MAXN] 用来标记DFS访问到该点时的次序/时间 LOW[MAXN]LOW[MAXN]LOW[MAXN] 用来储存子树从这一点可以访问到的点中访问时间最早的初始化为DFN也就是自身的访问时间。如果访问到了之前的点就会变成前面的点的时间戳。
这样对于之前的点来说就形成了一条从自身出发又回到自身的路径也就是一个强连通分量。
【算法实现】
对于每个点我们进行深搜对每个点打上时间戳给DFN和LOW赋值
然后对每一个没有访问过的点直接进行 访问并且将LOW的值改为所有后面访问点中最小的。 如果遇到一个访问过的点
如果他不在栈中就说明他和这个强连通分量没有任何关系在其他地方已经访问结束无法到这个点无法形成回路否则这个点肯定在栈中。这里着重需要理解栈中保存的是已经访问过的点中可以访问到这个点的点其他无关的点都已经弹出
如果这个已经访问的点在栈中就比较开心说明形成环了如果这个点的最小的时间戳小于他就保存一下LOW然后这个值就会回溯回去有可能访问的这个点在另一个小的强连通分量中所以我觉得应该比较LOW但是我看其他人的博客都是比较DFN仔细想了一下觉得也可以保存DFN的话也可以但是我还是觉得比较LOW的话LOW的值就可以代表是否存在在同一个强连通分量中更加优雅一些 。emm如果觉得不能理解可以先往下看不要在在意这些细节 。
最后DFS结束以后再回来看LOW的值是否改变如果没有改变说明这后面的所有点构成一个强连通分量然后全部弹出和他没有关系的早早弹出去了所以不用担心后面的没有关系的点怎么办
如果对一个点进行DFS改变LOW的值后LOW的值还没有改变仍然等于DFN说明从这一个点出发是无法回到更早的点的最早也就是自身也就是说他一定不是之前点的连通分量里面的否则通过它肯定能够访问到之前的点而之前的点的LOW都比较小所以这个LOW没有改变的点就是一个连通分量的根节点比较惨的话就只有他一个节点但也有可能他的子节点会访问到他形成连通分量但无论如何他都是根节点我们不妨用一个栈保存访问的顺序那么他后面访问的点肯定都是他的连通分量中的点全部弹出即可。如果不是的话后面的点肯定自成强连通分量那么肯定更早弹出了。 可能稍微有些懵先有个概念然后再看代码注意是递归处理的也就是访问到后面处理完了再返回来处理前面。
看着代码理解一下吧觉得哪里不能理解可以再看看上面的分析
void Trajan(int x)
{int v,tmp;DFN[x]LOW[x]idx; //赋给时间戳stack[top]x; vis[x]true;for(int ihead[x];i;iEdge[i].next){vEdge[i].v;if(!DFN[v]){Trajan(v);if(LOW[v]LOW[x]) LOW[x]LOW[v];}else if(vis[v] LOW[v]LOW[x]){LOW[x]LOW[v];}}if(DFN[x]LOW[x]){cnt;do{tmpstack[top--];vis[tmp]false;color[tmp]cnt;}while (tmp!x);}
}【样例题目】 Popular Cows
Every cows dream is to become the most popular cow in the herd. In a herd of N (1 N 10,000) cows, you are given up to M (1 M 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.Input
* Line 1: Two space-separated integers, N and M* Lines 2..1M: Two space-separated numbers A and B, meaning that A thinks B is popular.Output
*Line 1: A single integer that is the number of cows who are considered popular by every other cow.Sample Input
3 3
1 2
2 1
2 3Sample Output
1题目大意
有一群牛他们相互崇拜找出所有牛都崇拜的牛有多少
输入牛的个数n 崇拜的关系m,然后m行每行A,B,表示A崇拜B
输出被所有牛崇拜的牛的个数
【样例分析】 将崇拜的关系变成一个有向图处于一个强连通分量里面的牛肯定是相互崇拜的我们将一个强连通分量里面的所有牛看成一个点染色不同点重新形成一个图这个图里面唯一的出度为0的点中牛的个数就是答案。 因为出度为0的点肯定是被其他点里的牛崇拜的如果出度为0的点大于1的话两个出度为0的点里面的牛是没有办法崇拜的所以肯定不能被所有的牛崇拜所以如果出度为0的点不止一个答案就是0否则就是出度为0 的点里面牛的个数出度为0的点肯定是大于等于1的如果没有出度为0 的点那么他们形成了一个环而我们刚才说这是不同强连通分量如果只有一个连通分量就只有一个点也符合一个出度为0的点
【AC代码】
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int MAXN1e45;
const int MAXM5e45;
struct node
{int v,next;
}Edge[MAXM];
int head[MAXN],tot;
int DFN[MAXN],LOW[MAXN];
int color[MAXN],cnt;
bool vis[MAXN];
int idx;
int stack[MAXN],top;
int OutDegree[MAXN];
int n,m;void init()
{memset(head,0,sizeof(head)); tot0;idx0; memset(vis,0,sizeof(vis));memset(DFN,0,sizeof(DFN));memset(color,0,sizeof(color));cnt0; top0;memset(OutDegree,0,sizeof(OutDegree));
}void read()
{int u,v;for(int i0;im;i){scanf(%d%d,u,v);tot;Edge[tot].vv; Edge[tot].nexthead[u];head[u]tot;}
}void Trajan(int x)
{int v,tmp;DFN[x]LOW[x]idx;stack[top]x; vis[x]true;for(int ihead[x];i;iEdge[i].next){vEdge[i].v;if(!DFN[v]){Trajan(v);if(LOW[v]LOW[x]) LOW[x]LOW[v];}else if(vis[v] LOW[v]LOW[x]){LOW[x]LOW[v];}}if(DFN[x]LOW[x]){cnt;do{tmpstack[top--];vis[tmp]false;color[tmp]cnt;}while (tmp!x);}
}void solve()
{int v,mark,num,ans;for(int i1;in;i){if(!DFN[i])Trajan(i);}for(int i1;in;i){for(int jhead[i];j;jEdge[j].next){vEdge[j].v;if(color[i]!color[v])OutDegree[color[i]];}}num0; mark-1;for(int i1;icnt;i){if(!OutDegree[i]){num; marki;}}ans0;if(num!1){printf(0\n);}else{for(int i1;in;i){if(color[i]mark){ans;}}printf(%d\n,ans);}
}int main()
{while(~scanf(%d%d,n,m)){init();read();solve();}return 0;
}
