刚刚在算导上学会用两次dfs求SCC,终于过了前段时间群赛的一个题。
http://poj.org/problem?id=2762
题意:给定一个有向图,让你求它是否为半连通图(即对于图中任意两个顶点u,v 是否有u可以到达v或者v可以到达u)
解题思路:当时还不知道啥强连通分量,看了人家的一篇博客,了解了下解题思路,就是先求强连通分量+缩点,得到缩点以后的DAG(有向无环图),然后对缩点以后的图进行拓扑排序,如果有分叉则说明,原图不是半连通的(即从分叉处往下的两个分支,不能保证对于其中任意两个节点之间可达)。
关于该算法的正确性,算导上面证明的很清楚。
求SCC的步骤为:
1. 对原图进行dfs,求出每个结点的离开时间。
2. 按离开时间从后到前,对逆图进行dfs,每次dfs所到达的结点就组成一个强连通分量。(其实每个强连通分量可以看成一个点,然后这些点能构成一个DAG,至于如何保持SCC构成的DAG,其实可以用一个belong数组,belong[v]表示v结点属于哪一个强连通分量,这样在进行第二次dfs的时候如果搜索到已经被访问过的点上,并且该点在已经求出的强连通分量上,那么就把scc[belong[w]][now]置1,表示以前求出的强连通分量到当前正在求的强连通分量有一条边,不过我这里没想到这个好办法,我是把每个强连通分量里包含的顶点保存下来,如果搜索到已经访问过的结点就去以前求出的强连通分量里找该结点如果找到就在scc中添加一条边)
按上述顺序求出缩点以后的图,进行拓扑排序:
1. 每次取出所有结点中入度为0的并且没有被访问过的结点,如果这样的结点有多个,说明存在分支,则输出NO
2. 如果所有结点能按照1步骤进行排序,说明没有分支,则输出YES.
代码如下:
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1001;
int scc[MAXN][MAXN],vis[MAXN],f[MAXN],indeg[MAXN],scccnt;
vector<int> sccv[MAXN],g[MAXN],gt[MAXN];
bool find(int w,int i)
{
for(int j=0;j<sccv[w].size();j++)
if(sccv[w][j]==i)return true;
return false;
}
void dfs1(int v,int &time,int n)//cac the f array
{
vis[v] = 1;
for(int i=0;i<g[v].size();i++)
{
if(!vis[g[v][i]])dfs1(g[v][i],time,n);
}
f[time++] = v;
}
void dfs2(int v,int n)//mark one scc
{
vis[v] = 1;
sccv[scccnt].push_back(v);//the set of the scc's vertex
for(int i=0;i<gt[v].size();i++)
{
if(!vis[gt[v][i]])
dfs2(gt[v][i],n);
else
{
for(int j=scccnt-1;j>=0;j--)
{
if(find(j,gt[v][i]))//if find the scc which contain the vertex
{
scc[j][scccnt] = 1;//mark the scc graph
}
}
}
}
}
void SCC(int n)//cac all scc
{
for(int i=0;i<MAXN;i++)
sccv[i].clear();
memset(vis,0,sizeof(vis));
int time = 0;scccnt = 0;
for(int i=1;i<=n;i++)
{
if(!vis[i])dfs1(i,time,n);
}
memset(vis,0,sizeof(vis));
memset(scc,0,sizeof(scc));
for(int i=time-1;i>=0;i--)
{
if(!vis[f[i]])
{
dfs2(f[i],n);
scccnt++;
}
}
}
bool solve()//toposort
{
memset(indeg,0,sizeof(indeg));
for(int i=0;i<scccnt;i++)
{
for(int j=0;j<scccnt;j++)
{
if(scc[j][i])indeg[i]++;
}
}//cac indegree
memset(vis,0,sizeof(vis));
//toposort
for(int i=0;i<scccnt;i++)
{
int cnt=0,v=-1;
for(int j=0;j<scccnt;j++)
{
if(indeg[j]==0&&!vis[j])
{
cnt++;
v = j;
}
}
if(cnt!=1)return false;
vis[v] = 1;
for(int j=0;j<scccnt;j++)//update indegree
{
if(scc[v][j])indeg[j]--;
}
}
return true;
}
int main()
{
int n,t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
g[i].clear(),gt[i].clear();
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
gt[b].push_back(a);
}
SCC(n);
bool ok = solve();
if(ok) printf("Yes\n");
else printf("No\n");
}
return 0;
}
分享到:
相关推荐
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
给定一个图,你需要找出最长的一条由桥(边的删除会导致图变成多个连通分量)组成的路径。解决这个问题通常采用深度优先搜索(DFS)或广度优先搜索(BFS),同时维护两个数组,分别记录边的最小度和边的出现顺序,...
* 强连通分支及其缩点:例如 poj2186。 * 图的割边和割点:例如 poj3352。 * 最小割模型、网络流规约:例如 poj3308。 3. 数据结构: * 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态...
在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...
在实际问题中,例如POJ2186,题目要求找出所有通过传递关系都认为彼此受欢迎的奶牛数量,实质上就是求解强连通分量的规模。缩点操作是将强连通分量看作一个点,可以简化图的结构,便于后续处理。如果缩点后只有一个...
- (poj2186):如何找出一个有向图中的强连通分量。 5. **图的同构问题**: - (poj3352):判定两个图是否同构。 6. **小世界模型**: - (poj3308,):探索社交网络中的小世界现象。 ### 九、数据结构进阶 1. **...
2. **Kruskal算法**:首先对所有边按照权重从小到大排序,然后依次考虑每条边,如果这条边连接的两个顶点不在已经选择的边构成的连通分量中,就将其加入到最小生成树中。 理解最小生成树的算法是解决这类问题的关键...
3. **DFS或BFS**:通过遍历所有线段,对每一条线段进行搜索,确定其所在的连通分量,这可以通过DFS或BFS实现。 4. **计算结果**:最后,计算并查集中最大的集合个数,因为每个集合代表一组不相交的线段,我们需要...
- POJ 2186:强连通分量的识别与分析。 #### 最大流最小割 - **题目示例**: - POJ 3352:最大流问题的求解。 ### 数据结构 #### 栈 - **题目示例**: - POJ 2528、POJ 2828:栈的基本操作与应用场景。 #### ...
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
- **知识点**:双联通分量算法,用于识别图中的双连通部分。 #### 3189 Steady Cow Assignment - 网络流 - **知识点**:网络流算法。 #### 3204 Ikki's Story I - Road Reconstruction - 最大流 - **知识点**:...
3. **图算法的深化**:如差分约束系统、最小费用最大流、双连通分量、强连通分支及其缩点、图的割边和割点、最小割模型等。poj1201、poj2983等涉及这些高级图算法。 4. **高级数据结构**:如线段树、平衡树(Treap、...
割点,也称为关键顶点,是指在无向图中,如果移除该顶点及其所有相邻边,会导致图中至少有两个连通分量,即原图会断开成两个或更多个不相交的部分。 【描述】"POJ1523-SPF 【割点】 解题报告+AC代码+测试数据"表示...
4. **强连通分量**:识别图中的强连通分量(poj2186)。 5. **割点和桥**:识别图中的关键节点和边(poj3352)。 ### 十二、进阶数据结构 1. **高级数据结构**:如树状数组、线段树(poj2528, poj2828, poj2777, ...
- **定义**:找到图中的强连通分支并进行缩点。 - **示例题目**: - poj2186 - **应用场景**:适用于图的简化表示、复杂度降低。 **7. 图的割边** - **定义**:找到图中的割边。 - **应用场景**:适用于网络可靠性...
- **解法概述**:这是一个连通分量的问题,需要判断图中是否只有一个连通分量。 - **关键点**:正确理解连通性的定义,合理运用图的性质解决问题。 ### 14. POJ2553 - The Bottom of a Graph - **题目链接**:...
- **内容**: 对于一个无向图,双连通分量是指一个子图,在这个子图中任意两个顶点都是相互可达的。 - **示例题目**: poj3041, poj3020 #### 6. 匈牙利算法 - **内容**: 解决二分图最大匹配问题的算法。 - **示例...
6. **强连通分支和缩点**:在图理论中的高级概念,如POJ2186。 7. **图的割边和割点**:分析图的连接性和关键边点,如POJ3352。 8. **最小割模**:寻找图中的最小割,通常用于优化问题。 以上就是POJ平台中涉及到的...
2. **函数ALL_MST()**:遍历所有连通分量,调用`mst`函数计算各个连通分量的最小生成树,并将特殊节点s与各个连通分量的最小权值边加入生成树中。 3. **函数buildgraph(int m)**:读入原始图的数据,构建邻接矩阵`p...
有向图的强连通子图可以用来解决一些实际问题,例如在POJ2186受欢迎的奶牛问题中,要求计算被所有奶牛欢迎的奶牛的数目。这可以通过构建有向图,找到强连通子图,然后计算每个强连通子图中的点数来解决。 在解决强...