找到
1
篇与
Tarjan
相关的结果
-
【崇小】Tarjan及缩点（Tarjan基础Tarjan、受欢迎的牛cow） 主要算法 强连通分量Tarjan 强连通分量的缩点 P1：Tarjan基础 题目描述 问题描述 给定一张n个点，m条边组成的有向图，对于每个节点u，输出每个节点的dfn和low。 定义： dfn为节点u搜索的次序编号。 low为u或u的子树能够追溯到的最早的栈中节点的次序号。 加入in数组表示是否在栈内，同时考虑返祖边用dfn进行更新的情况。 输入 第一行n和m。 接下来m行u和v，表示u到v的边。 输出 n行，每行两个整数，分别表示dfn和low。 样例输入 3 3 1 2 2 1 2 3样例输出 1 1 2 1 3 3数据范围 n<=10000 题解报告 题目大意 给定一个有向图，要求使用Tarjan算法求出每个节点的深度优先数（dfn）和能追溯的最早祖先的dfn值（low），并按节点顺序输出这两个值。 解题思路 Tarjan算法的核心思想是通过深度优先搜索（DFS）遍历图中的所有节点，利用栈来跟踪当前搜索路径上的节点，并通过维护两个关键数组dfn和low来识别强连通分量（SCC）： dfn数组：记录每个节点被访问的时间戳（即DFS的访问顺序）。 low数组：记录当前节点或其子树能追溯到的最早栈中节点的dfn值。 具体步骤 初始化：对每个未被访问的节点启动DFS。初始化dfn和low为当前时间戳，并将节点压入栈。 遍历邻接点：对于当前节点的每个邻接点： 若邻接点未被访问，递归处理该邻接点，并用其low值更新当前节点的low值。 若邻接点已被访问且在栈中（属于当前路径），则用其dfn值更新当前节点的low值。 回溯处理：当DFS回溯到某个节点且其dfn等于low时，该节点为当前SCC的根，将栈中节点弹出直到当前节点，形成一个SCC。 Tips 题解报告按照标准程序2编写的。 标准程序 /* #include <bits/stdc++.h> using namespace std; const int N=10010; int i,n,m,x,y,t,dfn[N],low[N]; vector <int> f[N]; void dfs(int fx){ int i,sx;dfn[fx]=low[fx]=++t; for(i=0;i<f[fx].size();i++){ sx=f[fx][i]; if(dfn[sx]!=0) low[fx]=min(low[fx],low[sx]); else dfs(sx),low[fx]=min(low[fx],low[sx]); } } int main(){ cin>>n>>m; for(i=1;i<=m;i++) cin>>x>>y, f[x].push_back(y); for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i); for(i=1;i<=n;i++) cout<<dfn[i]<<" "<<low[i]<<"\n"; } */ //上面这段代码可能有错误，但是我认为是对的。 //下面这段代码是完全正确的 #include <bits/stdc++.h> using namespace std; const int N=10010; int i,j,n,m,x,y,t,cnt,ans,fx,sx,fl,g[N],b[N],dfn[N],low[N],a[N],in[N]; vector <int> f[N]; stack <int> st; void dfs(int fx){ int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1; for(i=0;i<f[fx].size();i++){ sx=f[fx][i]; if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]); else if(in[sx]) low[fx]=min(low[fx],dfn[sx]); } if(dfn[fx]==low[fx]){ cnt++; while(st.top()!=fx) a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop(); a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop(); } } int main(){ cin>>n>>m; for(i=1;i<=m;i++) cin>>x>>y, f[x].push_back(y); for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i); for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++){ fx=i;sx=f[i][j]; if(a[fx]!=a[sx]) g[a[fx]]++; } for(i=1;i<=cnt;i++) if(g[i]==0) fl++,ans+=b[i]; for(i=1;i<=n;i++) cout<<dfn[i]<<" "<<low[i]<<"\n"; }P2：Tarjan缩点（"受欢迎的奶牛"的铺垫） 题目描述 问题描述：sd 给定一张n个点，m条边组成的有向图。对这张图锁点，输出每个点属于第几个强联通分量。N<=10000 加入in数组表示是否在栈内，同时考虑返祖边用dfn进行更新的情况。 输入： 第一行n和m。 接下来m行u和v，表示u到v的边。 输出： 1行n个整数。 样例输入： 3 3 1 2 2 1 2 3样例输出： 2 2 1题解报告 题目大意 给定一个有向图，要求使用Tarjan算法求出每个节点所属的强连通分量（SCC），并按节点顺序输出其所属SCC的编号。SCC的编号顺序根据发现的逆序排列，即最后一个发现的SCC编号最大。 算法思路 Tarjan缩点算法通过DFS遍历图，识别强连通分量并为其分配唯一编号： DFS遍历：对每个未访问的节点启动DFS，维护dfn（访问时间戳）和low（当前节点能追溯的最早祖先的dfn）。 栈维护路径：用栈跟踪当前DFS路径上的节点，用in数组标记节点是否在栈中。 SCC识别：当回溯到某个节点且满足dfn[u] == low[u]时，该节点是当前SCC的根。将栈中节点弹出直到根节点，这些节点组成一个SCC，并分配唯一编号。 缩点记录：通过数组a记录每个节点所属的SCC编号。 标准程序 #include <bits/stdc++.h> using namespace std; const int N=10010; int i,n,m,x,y,t,cnt,dfn[N],low[N],a[N],in[N]; vector <int> f[N]; stack <int> st; void dfs(int fx){ int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1; for(i=0;i<f[fx].size();i++){ sx=f[fx][i]; if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]); else if(in[sx]) low[fx]=min(low[fx],dfn[sx]); } if(dfn[fx]==low[fx]){ cnt++; while(st.top()!=fx) a[st.top()]=cnt,in[st.top()]=0,st.pop(); a[st.top()]=cnt,in[st.top()]=0,st.pop(); } } int main(){ cin>>n>>m; for(i=1;i<=m;i++) cin>>x>>y, f[x].push_back(y); for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i); for(i=1;i<=n;i++) cout<<a[i]<<" "; }P3：受欢迎的牛 题目描述 【题目描述】cow.cpp 每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。 【输入】 第一行两个数 N,M； 接下来 M 行，每行两个数 A,B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A,B）。 【输出】 输出被除自己之外的所有牛认为是受欢迎的牛的数量。 【输入样例】 3 3 1 2 2 1 2 3【输出样例】 1样例说明 只有第三头牛被除自己之外的所有牛认为是受欢迎的。 数据范围： 对于全部数据，1≤N≤10^4,1≤M≤5×10^4。 题解报告 题目大意 给定一个包含N头牛和M条单向认可关系的有向图。要求找出被除自己之外所有其他牛认可的牛的数量。认可具有传递性，即若A认可B，B认可C，则A也认可C。 算法思路 核心思路：将问题转化为图论中的强连通分量（SCC）问题： 缩点处理：使用Tarjan算法将图中的强连通分量缩为单个节点，形成有向无环图（DAG）。 出度统计：在缩点后的DAG中，统计每个缩点的出度。 结果判定：若存在且仅存在一个出度为0的缩点，则该缩点包含的牛的数量即为答案；否则无解。 关键性质： 在DAG中，出度为0的节点是唯一可能被所有其他节点到达的节点。 若存在多个出度为0的节点，则这些节点之间无法相互到达，无法满足题意。 标准程序 #include <bits/stdc++.h> using namespace std; const int N=10010; int i,j,n,m,x,y,t,cnt,ans,fx,sx,fl,g[N],b[N],dfn[N],low[N],a[N],in[N]; vector <int> f[N]; stack <int> st; void dfs(int fx){ int i,sx;dfn[fx]=low[fx]=++t;st.push(fx);in[fx]=1; for(i=0;i<f[fx].size();i++){ sx=f[fx][i]; if(!dfn[sx]) dfs(sx),low[fx]=min(low[fx],low[sx]); else if(in[sx]) low[fx]=min(low[fx],dfn[sx]); } if(dfn[fx]==low[fx]){ cnt++; while(st.top()!=fx) a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop(); a[st.top()]=cnt,b[cnt]++,in[st.top()]=0,st.pop(); } } int main(){ cin>>n>>m; for(i=1;i<=m;i++) cin>>x>>y, f[x].push_back(y); for(i=1;i<=n;i++) if(dfn[i]==0) dfs(i); for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++){ fx=i;sx=f[i][j]; if(a[fx]!=a[sx]) g[a[fx]]++; } for(i=1;i<=cnt;i++) if(g[i]==0) fl++,ans+=b[i]; if(fl==1) cout<<ans; else cout<<0; }
