![题解：洛谷 B3609 [图论与代数结构 701] 强连通分量](images/news1.jpg)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B3609 [图论与代数结构 701] 强连通分量 - 洛谷【题目描述】给定一张n nn个点m mm条边的有向图求出其所有的强连通分量。注意本题可能存在重边和自环。【输入】第一行两个正整数n nnm mm表示图的点数和边数。接下来m mm行每行两个正整数u uu和v vv表示一条边。【输出】第一行一个整数表示这张图的强连通分量数目。接下来每行输出一个强连通分量。第一行输出1 11号点所在强连通分量第二行输出2 22号点所在强连通分量若已被输出则改为输出3 33号点所在强连通分量以此类推。每个强连通分量按节点编号大小输出。【输入样例】6 8 1 2 1 5 2 6 5 6 6 1 5 3 6 4 3 4【输出样例】3 1 2 5 6 3 4【算法标签】#普及plus【代码详解】#includebits/stdc.husingnamespacestd;constintN10005,M100005;intn,m;// n: 节点数m: 边数inth[N],e[M],ne[M],idx;// 邻接表存储图intdfn[N],low[N],tot;// dfn: DFS序low: 追溯值tot: 时间戳intstk[N],instk[N],top;// 栈和标记数组用于Tarjan算法intcon_cnt,con_size[N],con_id[N];// con_cnt: 强连通分量数量con_size: 每个分量的大小con_id: 每个节点所属的分量编号boolcon_print[N];// 标记是否已输出该强连通分量vectorintans[N];// 存储每个强连通分量的节点// 添加有向边a-bvoidadd(inta,intb){e[idx]b;// 边的终点ne[idx]h[a];// 指向a的下一条边h[a]idx;// 更新a的头节点}// Tarjan算法求强连通分量voidtarjan(intx){dfn[x]low[x]tot;// 初始化dfn和low为时间戳stk[top]x;// 节点入栈instk[x]1;// 标记节点在栈中for(intih[x];i!-1;ine[i])// 遍历x的所有邻接点{intye[i];// 邻接点yif(!dfn[y])// 如果y未被访问{tarjan(y);// 递归访问ylow[x]min(low[x],low[y]);// 更新low[x]}elseif(instk[y])// 如果y在栈中{low[x]min(low[x],dfn[y]);// 更新low[x]}}if(dfn[x]low[x])// 如果x是强连通分量的根{inty;con_cnt;// 增加强连通分量计数do{ystk[top--];// 弹出栈顶元素instk[y]0;// 标记不在栈中con_id[y]con_cnt;// 记录节点y所属的分量编号con_size[con_cnt];// 更新分量大小ans[con_cnt].push_back(y);// 将节点加入分量}while(y!x);// 直到弹出x为止}}intmain(){cinnm;// 输入节点数和边数memset(h,-1,sizeof(h));// 初始化邻接表while(m--)// 读入所有边{inta,b;cinab;add(a,b);// 添加有向边a-b}for(inti1;in;i)// 遍历所有节点if(dfn[i]0)// 如果节点未访问tarjan(i);// 执行Tarjan算法coutcon_cntendl;// 输出强连通分量数量for(inti1;icon_cnt;i)// 对每个分量的节点排序sort(ans[i].begin(),ans[i].end());for(inti1;in;i)// 按节点编号顺序输出{if(con_print[con_id[i]]true)// 如果该分量已输出跳过continue;for(intj0;jans[con_id[i]].size();j)// 输出分量内的所有节点coutans[con_id[i]][j] ;coutendl;con_print[con_id[i]]true;// 标记该分量已输出}return0;}【运行结果】6 8 1 2 1 5 2 6 5 6 6 1 5 3 6 4 3 4 3 1 2 5 6 3 4
题解：洛谷 B3609 [图论与代数结构 701] 强连通分量
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B3609 [图论与代数结构 701] 强连通分量 - 洛谷【题目描述】给定一张n nn个点m mm条边的有向图求出其所有的强连通分量。注意本题可能存在重边和自环。【输入】第一行两个正整数n nnm mm表示图的点数和边数。接下来m mm行每行两个正整数u uu和v vv表示一条边。【输出】第一行一个整数表示这张图的强连通分量数目。接下来每行输出一个强连通分量。第一行输出1 11号点所在强连通分量第二行输出2 22号点所在强连通分量若已被输出则改为输出3 33号点所在强连通分量以此类推。每个强连通分量按节点编号大小输出。【输入样例】6 8 1 2 1 5 2 6 5 6 6 1 5 3 6 4 3 4【输出样例】3 1 2 5 6 3 4【算法标签】#普及plus【代码详解】#includebits/stdc.husingnamespacestd;constintN10005,M100005;intn,m;// n: 节点数m: 边数inth[N],e[M],ne[M],idx;// 邻接表存储图intdfn[N],low[N],tot;// dfn: DFS序low: 追溯值tot: 时间戳intstk[N],instk[N],top;// 栈和标记数组用于Tarjan算法intcon_cnt,con_size[N],con_id[N];// con_cnt: 强连通分量数量con_size: 每个分量的大小con_id: 每个节点所属的分量编号boolcon_print[N];// 标记是否已输出该强连通分量vectorintans[N];// 存储每个强连通分量的节点// 添加有向边a-bvoidadd(inta,intb){e[idx]b;// 边的终点ne[idx]h[a];// 指向a的下一条边h[a]idx;// 更新a的头节点}// Tarjan算法求强连通分量voidtarjan(intx){dfn[x]low[x]tot;// 初始化dfn和low为时间戳stk[top]x;// 节点入栈instk[x]1;// 标记节点在栈中for(intih[x];i!-1;ine[i])// 遍历x的所有邻接点{intye[i];// 邻接点yif(!dfn[y])// 如果y未被访问{tarjan(y);// 递归访问ylow[x]min(low[x],low[y]);// 更新low[x]}elseif(instk[y])// 如果y在栈中{low[x]min(low[x],dfn[y]);// 更新low[x]}}if(dfn[x]low[x])// 如果x是强连通分量的根{inty;con_cnt;// 增加强连通分量计数do{ystk[top--];// 弹出栈顶元素instk[y]0;// 标记不在栈中con_id[y]con_cnt;// 记录节点y所属的分量编号con_size[con_cnt];// 更新分量大小ans[con_cnt].push_back(y);// 将节点加入分量}while(y!x);// 直到弹出x为止}}intmain(){cinnm;// 输入节点数和边数memset(h,-1,sizeof(h));// 初始化邻接表while(m--)// 读入所有边{inta,b;cinab;add(a,b);// 添加有向边a-b}for(inti1;in;i)// 遍历所有节点if(dfn[i]0)// 如果节点未访问tarjan(i);// 执行Tarjan算法coutcon_cntendl;// 输出强连通分量数量for(inti1;icon_cnt;i)// 对每个分量的节点排序sort(ans[i].begin(),ans[i].end());for(inti1;in;i)// 按节点编号顺序输出{if(con_print[con_id[i]]true)// 如果该分量已输出跳过continue;for(intj0;jans[con_id[i]].size();j)// 输出分量内的所有节点coutans[con_id[i]][j] ;coutendl;con_print[con_id[i]]true;// 标记该分量已输出}return0;}【运行结果】6 8 1 2 1 5 2 6 5 6 6 1 5 3 6 4 3 4 3 1 2 5 6 3 4
