HDU - 6165

news/2024/11/25 17:22:03/

题目链接:HDU - 6165


显然可以n次bfs,求连通性。但是时间卡得很紧。

这里我们可以 O(n+m)的复杂度解决。

先缩点变成DAG,然后缩点的图上跑Top,如果某一时刻,一个点可以让两个及以上的点度为0,那么显然就无解。否则有解。


AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1010;
int n,m,deg[N];
int low[N],dfn[N],vis[N],scc[N],co,cnt; stack<int> s;
vector<int> g[N],v[N];
inline int init(){for(int i=1;i<=n;i++)	dfn[i]=low[i]=deg[i]=scc[i]=0,g[i].clear(),v[i].clear(); cnt=co=0;
}
void Tarjan(int x){dfn[x]=low[x]=++cnt; vis[x]=1; s.push(x);for(auto to:g[x]){if(!dfn[to])	Tarjan(to),low[x]=min(low[x],low[to]);else if(vis[to])	low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){int u; co++;do{u=s.top(); s.pop(); scc[u]=co; vis[u]=0;}while(u!=x);}
}
void build_new_graph(){for(int i=1;i<=n;i++)for(auto to:g[i])	if(scc[i]!=scc[to]){v[scc[i]].push_back(scc[to]);	deg[scc[to]]++;}
}
int Top(){queue<int> q;	for(int i=1;i<=co;i++)	if(!deg[i])	q.push(i);if(q.size()>=2)	return 1;while(q.size()){int u=q.front();	q.pop();	int cnt=0;for(auto to:v[u]){if(--deg[to]==0)	q.push(to),cnt++;}if(cnt>=2)	return 1;}	return 0;
}
inline void solve(){cin>>n>>m;	init();for(int i=1,a,b;i<=m;i++)	scanf("%d %d",&a,&b),g[a].push_back(b);for(int i=1;i<=n;i++)	if(!dfn[i])	Tarjan(i);build_new_graph();puts(Top()?"Light my fire!":"I love you my love and our love save us!");
}
signed main(){int T;	cin>>T;while(T--)	solve();return 0;
}

http://www.ppmy.cn/news/507303.html

相关文章

hdu6155

Subsequence Count 题目链接 ccpc网络赛1006 题意是给一个01字符串&#xff0c;然后有2种操作&#xff0c; 1、把l到r这个区间的字符翻转&#xff0c; 2、查询l到r这个区间有多少个不同的子序列&#xff0c;&#xff08;注意是子序列&#xff0c;可不连续&#xff09;&…

IEC61850

IEC 61850是关于变电站自动化系统结构和数据通信的国际标准&#xff0c;目的是使变电站内不同厂家的智能电子设备(IED)之间通过一种标准实现互操作和信息共享&#xff0c;取消多种协议转换环节和转换设备&#xff0c;使系统调试更加便捷&#xff0c;实现“一个世界、一种技术、…

【面经】重庆农商行金融科技面经

【面经】重庆农商行金融科技面经 在脉脉上看重庆农商行貌似钱多事少&#xff0c;好评比较多。 公司介绍 重庆农村商业银行股份有限公司&#xff08;以下简称“重庆农商行”&#xff09;前身为重庆市农村信用社&#xff0c;成立于1951年&#xff0c;至今已有70余年历史。2003年…

联发科mt6165芯片原理图mt6165芯片资料

mt6165是在40nm cmos中实现的td-scdma和2g双模rf收发器。闯客网rf收发器函数是完全集成的。这份文件描述了rf的性能目标。在整个产品中嵌入宏 关键特征 -成本低的双模射频解决方案&#xff08;gge和td-scdma&#xff09;。8(hspa))四频gge(gsm850/900/dcs/pcs)/三频tdd(b34/b39…

Pyqt5的QThead线程对象实现线程开始、暂停、恢复、结束

前言 最近学习Pyqt5&#xff0c;研究QThead线程对象&#xff0c;因网上这方面资料较少&#xff0c;钻研过后&#xff0c;将感悟理解记录如下。 声明&#xff1a;感悟理解建立在分析其他大佬的博客的基础上&#xff0c;喝水不忘挖井人&#xff0c;大佬们的博客如下&#xff1a…

联想e480一键恢复小孔_thinkpade480win10如何一键还原

thinkpade480win10如何一键还原 卡饭网 本站整理 2019-08-14 方法一&#xff1a; 在控制面板中打开“恢复”(大图标查看方式下)。 点击【开始系统还原】 选择还原点 (1)系统还原会推荐一个最近的没有故障的还原点&#xff0c;建议选择。点击【下一步】&#xff0c;再点击【完成…

E480安装ubuntu18.04出现进入wifi没有无线适配器的处理方案

今天突发奇想&#xff0c;想在自己的电脑上装上ubuntu&#xff0c;实现win10ubuntu双系统 在顺利的装好系统之后&#xff0c;发现wifi界面找不到适配器&#xff0c;也即是无线网卡没有装好 E480是rtl8821ce无线网卡&#xff0c;官方不提供linux驱动&#xff0c;github上大佬写…

Java 基础进阶篇(十八):正则表达式匹配规则和应用

文章目录 一、正则表达式概述二、正则表达式的匹配规则三、正则表达式在方法中的应用3.1 校验手机号、邮箱和座机电话号码3.2 字符串的内容替换和分割 四、编程题目4.1 表示数值的字符串4.2 非严格递增连续数字序列 一、正则表达式概述 正则表达式是对字符串&#xff08;包括普…