返回

hdu6165 FFF at Valentine【强联通缩点+拓扑排序】

发布时间:2022-11-28 19:36:06 142
# php# c++

题目链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=6165​​

题意:给你一个无环,无重边的有向图,问你任意两点,是否存在路径使得其中一点能到达另一点

解析:一开始想着是强联通缩点以后的图,是否成一条链,WA了以后,发现了一个样例

后面想了一下,觉得应该是,强联通后拓扑排序,因为对于每一层来说只能有一个入度为零的点,若存在两个,那么就会存在一对点不可达

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
vectorG[maxn];
vectorrG[maxn];
vectorvs;
vectorg[maxn];
queue q;
int vis[maxn],cmp[maxn];
int in[maxn];
void init(int n)
{
for(int i=0; i<=n; i++)
{
G[i].clear();
rG[i].clear();
g[i].clear();
}
while(!q.empty()) q.pop();
}
void addEdge(int u,int v)
{
G[u].push_back(v);
rG[v].push_back(u);
}
void dfs(int u)
{
vis[u] = 1;
for(int i=0; i<(int)G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v])
dfs(v);
}
vs.push_back(u);
}
void rdfs(int u,int k)
{
vis[u] = 1;
cmp[u] = k;
for(int i=0; i<(int)rG[u].size(); i++)
{
int v = rG[u][i];
if(!vis[v])
rdfs(v,k);
}
}
int scc(int n)
{
memset(vis,0,sizeof(vis));
vs.clear();
for(int i=1; i<=n; i++)
{
if(!vis[i])
dfs(i);
}
memset(vis,0,sizeof(vis));
int k = 0;
for(int i=vs.size()-1; i>=0; i--)
{
if(!vis[vs[i]])
rdfs(vs[i],k++);
}
memset(in,0,sizeof(in));
for(int i=1; i<=n; i++)
{
for(int j=0; j<(int)G[i].size(); j++)
{
int v = G[i][j];
if(cmp[i]!=cmp[v])
{
in[cmp[v]]++;
g[cmp[i]].push_back(cmp[v]);
}
}
}
return k;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
init(n);
for(int i=0; i<m; i++)
{
int x,y;
scanf("%d %d",&x,&y);
addEdge(x,y);
}
int k=scc(n);
int flag=0;
for(int i=0; i<k; i++)
{
if(in[i]==0)
{
q.push(i);
flag++;
}
if(flag==2)
break;
}
if(flag<2)
{
while(!q.empty())
{
int now=q.front();
q.pop();
flag=0;
for(int i=0; i<(int)g[now].size(); i++)
{
int v=g[now][i];
in[v]--;
if(in[v]==0)
{
flag++;
q.push(v);
}
if(flag==2) break;
}
if(flag>=2) break;
}
}
if(flag>=1)
puts("Light my fire!");
else
puts("I love you my love and our love save us!");
}
return 0;
}

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
hdu6033 Add More Zero 2022-11-28 19:07:38