#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
vector<int> g[MAXN];//adjlist
stack<int> S,P;
int belong[MAXN],vis[MAXN],indeg[MAXN],sccg[MAXN][MAXN],scccnt,disc[MAXN];
void init()
{
for(int i=0;i<MAXN;i++)g[i].clear();
memset(belong,-1,sizeof(belong));
memset(vis,0,sizeof(vis));
scccnt = 0;
memset(sccg,0,sizeof(sccg));
memset(indeg,0,sizeof(indeg));
while(!S.empty())S.pop();
while(!P.empty())P.pop();
}
void dfs_scc(int u,int &time)
{
disc[u] = time++;
S.push(u);
P.push(u);
vis[u] = 1;
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i];
if(!vis[v])
{
dfs_scc(v,time);
}
else if(belong[v]==-1)
{
while(disc[P.top()]>disc[v])P.pop();
}
}
if(P.top()==u)
{
while(S.top()!=u)
{
int v = S.top();
belong[v] = scccnt;
S.pop();
}
S.pop();
belong[u] = scccnt;
P.pop();
scccnt++;
}
}
void Gabow(int n)
{
int time = 0;
for(int i=1;i<=n;i++)
{
if(!vis[i])dfs_scc(i,time);
}
}
void make_sccg(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
if(belong[i]!=belong[g[i][j]])
{
sccg[belong[i]][belong[g[i][j]]]=1;
}
}
}
}
void cac_indeg()
{
for(int i=0;i<scccnt;i++)
{
for(int j=0;j<scccnt;j++)
{
if(sccg[j][i])indeg[i]++;
}
}
}
bool solve(int n)
{
Gabow(n);
make_sccg(n);
cac_indeg();
memset(vis,0,sizeof(vis));
for(int i=0;i<scccnt;i++)
{
int cnt=0,v;
for(int j=0;j<scccnt;j++)
{
if(indeg[j]==0&&!vis[j])v=j,cnt++;
}
if(cnt!=1)return false;
vis[v] = 1;
for(int w=0;w<scccnt;w++)
{
if(sccg[v][w])indeg[w]--;
}
}
return true;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
}
bool ok = solve(n);
if(ok) printf("Yes\n");
else printf("No\n");
}
return 0;
}
分享到:
相关推荐
SCC(Self-Consistent Clustering,自洽聚类)是一种在图像分类领域广泛应用的算法。它基于数据的内在结构和相似性,通过迭代过程来不断优化聚类结果,达到自洽状态,即聚类结果与原始数据的相似度矩阵一致。在...
标题中的"SCC.rar_SCC_VC 串口"指的是一个使用VC++开发的串口通信监控软件,名为SCC(可能代表Serial Communication Controller)。这个软件主要用于通过串行接口与外部设备进行数据交换,并且其用户界面设计采用了...
《欧姆龙安全产品Sge_Scc_Ca_C_8_2.pdf》是欧姆龙公司推出的关于其安全产品系列的详细说明书。该文档主要涵盖了欧姆龙的SGE和SCC系列的安全传感器,这些产品在工业自动化领域广泛应用,旨在确保工作场所的安全,预防...
标题"SCC_SerialVC++_Vc_strengthim4_"暗示了这是一个关于使用VC++实现串口控制的应用,而“strengthim4”可能是指程序的特定功能或版本号。 串口通信的基础知识是理解COM端口,它是计算机与外部设备通信的接口。在...
本项目"modRankineSCC-master_rankine_matlab_SCC_"是通过MATLAB编程实现的,目的是计算变工况下兰金循环的性能参数,特别是采用SCC(Supercritical Carbon Dioxide,超临界二氧化碳)作为工质的情况。 超临界二...
对CAD的图元或者图元的相对距离零碎数归整,如端点、顶点、线段的 ;;;长度的零碎数归整,轴线之间距取整等等。 ;;;适用于斯维尔,天正,直线,圆,弧,多段线,块。...譬如歪斜不平的线段可以摆平,轴线间距归整,Z...
在这个场景中,我们关注的是“基于稀疏表示的聚类算法”(Sparse Representation-based Clustering, 简称SCC),这是一种融合了稀疏表示理论和聚类算法的创新技术。 稀疏表示的概念源于信号处理和机器学习,其核心...
让VC的IDE也能随意的使用CVS的插件
欧姆龙公司提供的这份产品样本介绍了一款名为SGE/SCC的新安全边产品系列,该产品主要应用于机械设备的安全保护。SGE(SafetyEdge)安全边是一种安装于机械设备移动部件如门和围栏上的安全传感器,当检测到与人员或...
SCC的关键函数主要包括两个部分:稀疏编码和子空间一致性。稀疏编码阶段,每个数据点被表示为其他数据点的线性组合,且这种组合尽可能地稀疏,即大多数系数为零。这可以通过优化问题来实现,例如最小化L1范数(鼓励...
报告概述了IBM在2012年为波士顿市提供的Smarter Cities Challenge项目,作为IBM建设更智能地球公民计划的一部分。该项目旨在通过解锁、分享和分析交通数据,帮助波士顿实现气候和交通改善目标。...
安全中心整站系统是一个网络安全类整站系统。由七个模块组成,其中包括:文章系统(安全文档)、下载系统(安全工具、**作品)、漏洞发布系统(安全漏洞)、代码发布模块(漏洞利用)、在线申请模块(工作室)和信息...
"connected component"和"scc_java"标签表明这个程序或数据集关注的是寻找有向图的强连通分量。"强连通"指的是图中的一种特定结构,"有向图"则明确了图的类型。 描述中提到的算法是递归地求解有向图的强连通分量。...
ASP源码,压缩包解压密码:www.cqlsoft.com
【标题】"SCC_Project:羊和狼,meeeeeee" 暗示这是一个与游戏或模拟相关的项目,其中可能包含“羊”和“狼”这两个元素的角色或逻辑。"SCC"通常代表Strongly Connected Components,这在图论中是一个重要的概念,...
【标题】"CS131_02_SCC_Polymorphism活动" 指的是一场关于计算机科学课程CS131中的第二部分,主题是"结构化并发与控制(Structured Concurrency and Control)",重点探讨的是多态性(Polymorphism)在编程中的应用...
仅标头的库,用于并行查找强连接的组件用法示例: # include < vector># include < thread># include < cassert># include " parallel_union_find/algorithm/multi_core_on_the_fly_scc_decomposition_algorithm.hpp...
FTP(File Transfer Protocol)是一种广泛使用的网络协议,用于在互联网上进行文件的上传和下载。在VB(Visual Basic)环境中,开发FTP客户端程序可以方便地实现这一功能。VB FTP客户端通常涉及以下关键知识点: ...
【标题】"SCC.rar_C编译器_SCC"指的是一个名为SCC的C语言编译器项目,它被封装在一个RAR压缩包中。SCC是Simple C Compiler的缩写,意味着这是一个为了理解和学习编译原理而设计的简单C语言编译器。这个项目可能包含...
《SCC:深入理解编译器词法分析器》 在计算机科学领域,编译器是将高级语言转化为机器语言的重要工具,而词法分析器则是编译器的第一道工序,它负责识别源代码中的词汇元素,为后续的语法分析和语义分析打下基础。...