贴模板,备忘。

模板1:

 #include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct node {
int v,next;
}edge[];
int DFN[],LOW[];
int stack[],heads[],visit[],cnt,tot,index;
void add(int x,int y)
{
edge[++cnt].next=heads[x];
edge[cnt].v = y;
heads[x]=cnt;
return ;
}
void tarjan(int x)//代表第几个点在处理。递归的是点。
{
DFN[x]=LOW[x]=++tot;// 新进点的初始化。
stack[++index]=x;//进站
visit[x]=;//表示在栈里
for(int i=heads[x];i!=-;i=edge[i].next)
{
if(!DFN[edge[i].v]) {//如果没访问过
tarjan(edge[i].v);//往下进行延伸,开始递归
LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
}
else if(visit[edge[i].v ]){ //如果访问过,并且还在栈里。
LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子/父亲。就是链接对应关系
}
}
if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
{
do{
printf("%d ",stack[index]);
visit[stack[index]]=;
index--;
}while(x!=stack[index+]);//出栈,并且输出。
printf("\n");
}
return ;
}
int main()
{
memset(heads,-,sizeof(heads));
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++)
if(!DFN[i]) tarjan(i);//当这个点没有访问过,就从此点开始。防止图没走完
return ;
}

模板2:

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#define maxn 1005
using namespace std;
struct Edge
{
int next;
int to;
}edge[maxn];
int head[maxn];
int cnt;
int step;
int dfn[maxn];//表示深搜的步数;
int low[maxn];//表示能追溯到最早的栈中节点的次序;
int sccno[maxn];//缩点数组,表示每个点对应的缩点值;
int scc_cnt;//强连通分量的个数;
void init()
{
cnt=;
step=;
memset(head,-,sizeof(head));
}
void add(int u,int v)
{
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt++;
}
vector<int>scc[maxn];//得出来的缩点,保存具体缩了那些点;
stack<int>s;
void dfs(int u)
{
dfn[u]=low[u]=++step;
s.push(u);
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(!dfn[v])
{
dfs(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++;
scc[scc_cnt].clear();
while()
{
int x=s.top();
s.pop();
if(sccno[x]!=scc_cnt)
scc[scc_cnt].push_back(x);
sccno[x]=scc_cnt;
if(x==u)
break;
}
}
}
void tarjan(int n)
{
memset(sccno,,sizeof(sccno));
memset(dfn,,sizeof(dfn));
step=scc_cnt=;
for(int i=;i<=n;i++)
if(!dfn[i])dfs(i);
}
int main()
{
int n,m;
int x,y;
cin>>n>>m;
init();
while(m--)
{
cin>>x>>y;
add(x,y);
}
tarjan(n);
cout<<scc_cnt<<endl;
return ;
}

滚了。

最新文章

  1. dom 无法找到 body节点问题
  2. WPF系列:无边框窗口
  3. java设计模式(六) 命令模式
  4. /etc/profile和$HOME/.bash_profile
  5. 关于Android的onResume的2点体会(程序切换之后恢复状态)
  6. 对java面试文章的技术漫谈的C#技术理解
  7. [转载][记录]javascript生成不重复的随机数
  8. 关于STM32 RTC的使用
  9. EBS R12 修改 apps 密码[Z]
  10. COB (Chip On Board) 製程介紹/簡介/注意事項 I
  11. linux 进程命令
  12. java 数据结构 栈的实现
  13. JS在可编辑的div中的光标位置插入内容或表情
  14. Confluence 6 已经存在的 Confluence 安装配置一个数据源连接
  15. JDK7和JDK8concurrentHashmap区别
  16. Maven 下载安装
  17. 【stylus】stylus在webstrom中的识别
  18. (转) centos7下创建mysql5.6多实例
  19. linux下的shell运算(加、减、乘、除
  20. php 换行 PHP_EOL

热门文章

  1. 离线安装 Visual Studio Express 而不下载整个镜像文件的方法(转载)
  2. LightOJ - 1341 Aladdin and the Flying Carpet(数论)
  3. German Collegiate Programming Contest 2018​ C. Coolest Ski Route
  4. billard:桌球的走位路线图解
  5. 读取手机联系人,并用listview显示
  6. 关于tree节点的刷新
  7. cf965c Greedy Arkady
  8. 【Two Sum】cpp
  9. 初识面向对象-python
  10. Linux常用命令与基本概念